]> git.lizzy.rs Git - rust.git/blob - src/librustdoc/clean/mod.rs
f446bf587bdcd0c30f904f351a789c13773638a1
[rust.git] / src / librustdoc / clean / mod.rs
1 // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! This module contains the "cleaned" pieces of the AST, and the functions
12 //! that clean them.
13
14 pub use self::Type::*;
15 pub use self::Mutability::*;
16 pub use self::ItemEnum::*;
17 pub use self::TyParamBound::*;
18 pub use self::SelfTy::*;
19 pub use self::FunctionRetTy::*;
20 pub use self::Visibility::*;
21
22 use syntax::abi::Abi;
23 use syntax::ast;
24 use syntax::attr;
25 use syntax::codemap::Spanned;
26 use syntax::ptr::P;
27 use syntax::symbol::keywords;
28 use syntax_pos::{self, DUMMY_SP, Pos};
29
30 use rustc::middle::privacy::AccessLevels;
31 use rustc::middle::resolve_lifetime as rl;
32 use rustc::middle::lang_items;
33 use rustc::hir::def::{Def, CtorKind};
34 use rustc::hir::def_id::{CrateNum, DefId, CRATE_DEF_INDEX, LOCAL_CRATE};
35 use rustc::ty::subst::Substs;
36 use rustc::ty::{self, AdtKind};
37 use rustc::middle::stability;
38 use rustc::util::nodemap::{FxHashMap, FxHashSet};
39 use rustc_typeck::hir_ty_to_ty;
40
41 use rustc::hir;
42
43 use std::{mem, slice, vec};
44 use std::path::PathBuf;
45 use std::rc::Rc;
46 use std::sync::Arc;
47 use std::u32;
48
49 use core::DocContext;
50 use doctree;
51 use visit_ast;
52 use html::item_type::ItemType;
53
54 pub mod inline;
55 pub mod cfg;
56 mod simplify;
57
58 use self::cfg::Cfg;
59
60 // extract the stability index for a node from tcx, if possible
61 fn get_stability(cx: &DocContext, def_id: DefId) -> Option<Stability> {
62     cx.tcx.lookup_stability(def_id).clean(cx)
63 }
64
65 fn get_deprecation(cx: &DocContext, def_id: DefId) -> Option<Deprecation> {
66     cx.tcx.lookup_deprecation(def_id).clean(cx)
67 }
68
69 pub trait Clean<T> {
70     fn clean(&self, cx: &DocContext) -> T;
71 }
72
73 impl<T: Clean<U>, U> Clean<Vec<U>> for [T] {
74     fn clean(&self, cx: &DocContext) -> Vec<U> {
75         self.iter().map(|x| x.clean(cx)).collect()
76     }
77 }
78
79 impl<T: Clean<U>, U> Clean<U> for P<T> {
80     fn clean(&self, cx: &DocContext) -> U {
81         (**self).clean(cx)
82     }
83 }
84
85 impl<T: Clean<U>, U> Clean<U> for Rc<T> {
86     fn clean(&self, cx: &DocContext) -> U {
87         (**self).clean(cx)
88     }
89 }
90
91 impl<T: Clean<U>, U> Clean<Option<U>> for Option<T> {
92     fn clean(&self, cx: &DocContext) -> Option<U> {
93         self.as_ref().map(|v| v.clean(cx))
94     }
95 }
96
97 impl<T, U> Clean<U> for ty::Binder<T> where T: Clean<U> {
98     fn clean(&self, cx: &DocContext) -> U {
99         self.0.clean(cx)
100     }
101 }
102
103 impl<T: Clean<U>, U> Clean<Vec<U>> for P<[T]> {
104     fn clean(&self, cx: &DocContext) -> Vec<U> {
105         self.iter().map(|x| x.clean(cx)).collect()
106     }
107 }
108
109 #[derive(Clone, Debug)]
110 pub struct Crate {
111     pub name: String,
112     pub src: PathBuf,
113     pub module: Option<Item>,
114     pub externs: Vec<(CrateNum, ExternalCrate)>,
115     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
116     pub access_levels: Arc<AccessLevels<DefId>>,
117     // These are later on moved into `CACHEKEY`, leaving the map empty.
118     // Only here so that they can be filtered through the rustdoc passes.
119     pub external_traits: FxHashMap<DefId, Trait>,
120 }
121
122 impl<'a, 'tcx> Clean<Crate> for visit_ast::RustdocVisitor<'a, 'tcx> {
123     fn clean(&self, cx: &DocContext) -> Crate {
124         use ::visit_lib::LibEmbargoVisitor;
125
126         {
127             let mut r = cx.renderinfo.borrow_mut();
128             r.deref_trait_did = cx.tcx.lang_items.deref_trait();
129             r.deref_mut_trait_did = cx.tcx.lang_items.deref_mut_trait();
130             r.owned_box_did = cx.tcx.lang_items.owned_box();
131         }
132
133         let mut externs = Vec::new();
134         for cnum in cx.sess().cstore.crates() {
135             externs.push((cnum, cnum.clean(cx)));
136             // Analyze doc-reachability for extern items
137             LibEmbargoVisitor::new(cx).visit_lib(cnum);
138         }
139         externs.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
140
141         // Clean the crate, translating the entire libsyntax AST to one that is
142         // understood by rustdoc.
143         let mut module = self.module.clean(cx);
144
145         let ExternalCrate { name, src, primitives, .. } = LOCAL_CRATE.clean(cx);
146         {
147             let m = match module.inner {
148                 ModuleItem(ref mut m) => m,
149                 _ => unreachable!(),
150             };
151             m.items.extend(primitives.iter().map(|&(def_id, prim, ref attrs)| {
152                 Item {
153                     source: Span::empty(),
154                     name: Some(prim.to_url_str().to_string()),
155                     attrs: attrs.clone(),
156                     visibility: Some(Public),
157                     stability: get_stability(cx, def_id),
158                     deprecation: get_deprecation(cx, def_id),
159                     def_id,
160                     inner: PrimitiveItem(prim),
161                 }
162             }));
163         }
164
165         let mut access_levels = cx.access_levels.borrow_mut();
166         let mut external_traits = cx.external_traits.borrow_mut();
167
168         Crate {
169             name,
170             src,
171             module: Some(module),
172             externs,
173             primitives,
174             access_levels: Arc::new(mem::replace(&mut access_levels, Default::default())),
175             external_traits: mem::replace(&mut external_traits, Default::default()),
176         }
177     }
178 }
179
180 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
181 pub struct ExternalCrate {
182     pub name: String,
183     pub src: PathBuf,
184     pub attrs: Attributes,
185     pub primitives: Vec<(DefId, PrimitiveType, Attributes)>,
186 }
187
188 impl Clean<ExternalCrate> for CrateNum {
189     fn clean(&self, cx: &DocContext) -> ExternalCrate {
190         let root = DefId { krate: *self, index: CRATE_DEF_INDEX };
191         let krate_span = cx.tcx.def_span(root);
192         let krate_src = cx.sess().codemap().span_to_filename(krate_span);
193
194         // Collect all inner modules which are tagged as implementations of
195         // primitives.
196         //
197         // Note that this loop only searches the top-level items of the crate,
198         // and this is intentional. If we were to search the entire crate for an
199         // item tagged with `#[doc(primitive)]` then we would also have to
200         // search the entirety of external modules for items tagged
201         // `#[doc(primitive)]`, which is a pretty inefficient process (decoding
202         // all that metadata unconditionally).
203         //
204         // In order to keep the metadata load under control, the
205         // `#[doc(primitive)]` feature is explicitly designed to only allow the
206         // primitive tags to show up as the top level items in a crate.
207         //
208         // Also note that this does not attempt to deal with modules tagged
209         // duplicately for the same primitive. This is handled later on when
210         // rendering by delegating everything to a hash map.
211         let as_primitive = |def: Def| {
212             if let Def::Mod(def_id) = def {
213                 let attrs = cx.tcx.get_attrs(def_id).clean(cx);
214                 let mut prim = None;
215                 for attr in attrs.lists("doc") {
216                     if let Some(v) = attr.value_str() {
217                         if attr.check_name("primitive") {
218                             prim = PrimitiveType::from_str(&v.as_str());
219                             if prim.is_some() {
220                                 break;
221                             }
222                         }
223                     }
224                 }
225                 return prim.map(|p| (def_id, p, attrs));
226             }
227             None
228         };
229         let primitives = if root.is_local() {
230             cx.tcx.hir.krate().module.item_ids.iter().filter_map(|&id| {
231                 let item = cx.tcx.hir.expect_item(id.id);
232                 match item.node {
233                     hir::ItemMod(_) => {
234                         as_primitive(Def::Mod(cx.tcx.hir.local_def_id(id.id)))
235                     }
236                     hir::ItemUse(ref path, hir::UseKind::Single)
237                     if item.vis == hir::Visibility::Public => {
238                         as_primitive(path.def).map(|(_, prim, attrs)| {
239                             // Pretend the primitive is local.
240                             (cx.tcx.hir.local_def_id(id.id), prim, attrs)
241                         })
242                     }
243                     _ => None
244                 }
245             }).collect()
246         } else {
247             cx.tcx.sess.cstore.item_children(root, cx.tcx.sess).iter().map(|item| item.def)
248               .filter_map(as_primitive).collect()
249         };
250
251         ExternalCrate {
252             name: cx.tcx.crate_name(*self).to_string(),
253             src: PathBuf::from(krate_src),
254             attrs: cx.tcx.get_attrs(root).clean(cx),
255             primitives,
256         }
257     }
258 }
259
260 /// Anything with a source location and set of attributes and, optionally, a
261 /// name. That is, anything that can be documented. This doesn't correspond
262 /// directly to the AST's concept of an item; it's a strict superset.
263 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
264 pub struct Item {
265     /// Stringified span
266     pub source: Span,
267     /// Not everything has a name. E.g., impls
268     pub name: Option<String>,
269     pub attrs: Attributes,
270     pub inner: ItemEnum,
271     pub visibility: Option<Visibility>,
272     pub def_id: DefId,
273     pub stability: Option<Stability>,
274     pub deprecation: Option<Deprecation>,
275 }
276
277 impl Item {
278     /// Finds the `doc` attribute as a NameValue and returns the corresponding
279     /// value found.
280     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
281         self.attrs.doc_value()
282     }
283     pub fn is_crate(&self) -> bool {
284         match self.inner {
285             StrippedItem(box ModuleItem(Module { is_crate: true, ..})) |
286             ModuleItem(Module { is_crate: true, ..}) => true,
287             _ => false,
288         }
289     }
290     pub fn is_mod(&self) -> bool {
291         self.type_() == ItemType::Module
292     }
293     pub fn is_trait(&self) -> bool {
294         self.type_() == ItemType::Trait
295     }
296     pub fn is_struct(&self) -> bool {
297         self.type_() == ItemType::Struct
298     }
299     pub fn is_enum(&self) -> bool {
300         self.type_() == ItemType::Enum
301     }
302     pub fn is_fn(&self) -> bool {
303         self.type_() == ItemType::Function
304     }
305     pub fn is_associated_type(&self) -> bool {
306         self.type_() == ItemType::AssociatedType
307     }
308     pub fn is_associated_const(&self) -> bool {
309         self.type_() == ItemType::AssociatedConst
310     }
311     pub fn is_method(&self) -> bool {
312         self.type_() == ItemType::Method
313     }
314     pub fn is_ty_method(&self) -> bool {
315         self.type_() == ItemType::TyMethod
316     }
317     pub fn is_typedef(&self) -> bool {
318         self.type_() == ItemType::Typedef
319     }
320     pub fn is_primitive(&self) -> bool {
321         self.type_() == ItemType::Primitive
322     }
323     pub fn is_union(&self) -> bool {
324         self.type_() == ItemType::Union
325     }
326     pub fn is_import(&self) -> bool {
327         self.type_() == ItemType::Import
328     }
329
330     pub fn is_stripped(&self) -> bool {
331         match self.inner { StrippedItem(..) => true, _ => false }
332     }
333     pub fn has_stripped_fields(&self) -> Option<bool> {
334         match self.inner {
335             StructItem(ref _struct) => Some(_struct.fields_stripped),
336             UnionItem(ref union) => Some(union.fields_stripped),
337             VariantItem(Variant { kind: VariantKind::Struct(ref vstruct)} ) => {
338                 Some(vstruct.fields_stripped)
339             },
340             _ => None,
341         }
342     }
343
344     pub fn stability_class(&self) -> Option<String> {
345         self.stability.as_ref().and_then(|ref s| {
346             let mut classes = Vec::with_capacity(2);
347
348             if s.level == stability::Unstable {
349                 classes.push("unstable");
350             }
351
352             if !s.deprecated_since.is_empty() {
353                 classes.push("deprecated");
354             }
355
356             if classes.len() != 0 {
357                 Some(classes.join(" "))
358             } else {
359                 None
360             }
361         })
362     }
363
364     pub fn stable_since(&self) -> Option<&str> {
365         self.stability.as_ref().map(|s| &s.since[..])
366     }
367
368     /// Returns a documentation-level item type from the item.
369     pub fn type_(&self) -> ItemType {
370         ItemType::from(self)
371     }
372 }
373
374 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
375 pub enum ItemEnum {
376     ExternCrateItem(String, Option<String>),
377     ImportItem(Import),
378     StructItem(Struct),
379     UnionItem(Union),
380     EnumItem(Enum),
381     FunctionItem(Function),
382     ModuleItem(Module),
383     TypedefItem(Typedef, bool /* is associated type */),
384     StaticItem(Static),
385     ConstantItem(Constant),
386     TraitItem(Trait),
387     ImplItem(Impl),
388     /// A method signature only. Used for required methods in traits (ie,
389     /// non-default-methods).
390     TyMethodItem(TyMethod),
391     /// A method with a body.
392     MethodItem(Method),
393     StructFieldItem(Type),
394     VariantItem(Variant),
395     /// `fn`s from an extern block
396     ForeignFunctionItem(Function),
397     /// `static`s from an extern block
398     ForeignStaticItem(Static),
399     MacroItem(Macro),
400     PrimitiveItem(PrimitiveType),
401     AssociatedConstItem(Type, Option<String>),
402     AssociatedTypeItem(Vec<TyParamBound>, Option<Type>),
403     DefaultImplItem(DefaultImpl),
404     /// An item that has been stripped by a rustdoc pass
405     StrippedItem(Box<ItemEnum>),
406 }
407
408 impl ItemEnum {
409     pub fn generics(&self) -> Option<&Generics> {
410         Some(match *self {
411             ItemEnum::StructItem(ref s) => &s.generics,
412             ItemEnum::EnumItem(ref e) => &e.generics,
413             ItemEnum::FunctionItem(ref f) => &f.generics,
414             ItemEnum::TypedefItem(ref t, _) => &t.generics,
415             ItemEnum::TraitItem(ref t) => &t.generics,
416             ItemEnum::ImplItem(ref i) => &i.generics,
417             ItemEnum::TyMethodItem(ref i) => &i.generics,
418             ItemEnum::MethodItem(ref i) => &i.generics,
419             ItemEnum::ForeignFunctionItem(ref f) => &f.generics,
420             _ => return None,
421         })
422     }
423 }
424
425 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
426 pub struct Module {
427     pub items: Vec<Item>,
428     pub is_crate: bool,
429 }
430
431 impl Clean<Item> for doctree::Module {
432     fn clean(&self, cx: &DocContext) -> Item {
433         let name = if self.name.is_some() {
434             self.name.unwrap().clean(cx)
435         } else {
436             "".to_string()
437         };
438
439         let mut items: Vec<Item> = vec![];
440         items.extend(self.extern_crates.iter().map(|x| x.clean(cx)));
441         items.extend(self.imports.iter().flat_map(|x| x.clean(cx)));
442         items.extend(self.structs.iter().map(|x| x.clean(cx)));
443         items.extend(self.unions.iter().map(|x| x.clean(cx)));
444         items.extend(self.enums.iter().map(|x| x.clean(cx)));
445         items.extend(self.fns.iter().map(|x| x.clean(cx)));
446         items.extend(self.foreigns.iter().flat_map(|x| x.clean(cx)));
447         items.extend(self.mods.iter().map(|x| x.clean(cx)));
448         items.extend(self.typedefs.iter().map(|x| x.clean(cx)));
449         items.extend(self.statics.iter().map(|x| x.clean(cx)));
450         items.extend(self.constants.iter().map(|x| x.clean(cx)));
451         items.extend(self.traits.iter().map(|x| x.clean(cx)));
452         items.extend(self.impls.iter().flat_map(|x| x.clean(cx)));
453         items.extend(self.macros.iter().map(|x| x.clean(cx)));
454         items.extend(self.def_traits.iter().map(|x| x.clean(cx)));
455
456         // determine if we should display the inner contents or
457         // the outer `mod` item for the source code.
458         let whence = {
459             let cm = cx.sess().codemap();
460             let outer = cm.lookup_char_pos(self.where_outer.lo());
461             let inner = cm.lookup_char_pos(self.where_inner.lo());
462             if outer.file.start_pos == inner.file.start_pos {
463                 // mod foo { ... }
464                 self.where_outer
465             } else {
466                 // mod foo; (and a separate FileMap for the contents)
467                 self.where_inner
468             }
469         };
470
471         Item {
472             name: Some(name),
473             attrs: self.attrs.clean(cx),
474             source: whence.clean(cx),
475             visibility: self.vis.clean(cx),
476             stability: self.stab.clean(cx),
477             deprecation: self.depr.clean(cx),
478             def_id: cx.tcx.hir.local_def_id(self.id),
479             inner: ModuleItem(Module {
480                is_crate: self.is_crate,
481                items,
482             })
483         }
484     }
485 }
486
487 pub struct ListAttributesIter<'a> {
488     attrs: slice::Iter<'a, ast::Attribute>,
489     current_list: vec::IntoIter<ast::NestedMetaItem>,
490     name: &'a str
491 }
492
493 impl<'a> Iterator for ListAttributesIter<'a> {
494     type Item = ast::NestedMetaItem;
495
496     fn next(&mut self) -> Option<Self::Item> {
497         if let Some(nested) = self.current_list.next() {
498             return Some(nested);
499         }
500
501         for attr in &mut self.attrs {
502             if let Some(list) = attr.meta_item_list() {
503                 if attr.check_name(self.name) {
504                     self.current_list = list.into_iter();
505                     if let Some(nested) = self.current_list.next() {
506                         return Some(nested);
507                     }
508                 }
509             }
510         }
511
512         None
513     }
514 }
515
516 pub trait AttributesExt {
517     /// Finds an attribute as List and returns the list of attributes nested inside.
518     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a>;
519 }
520
521 impl AttributesExt for [ast::Attribute] {
522     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
523         ListAttributesIter {
524             attrs: self.iter(),
525             current_list: Vec::new().into_iter(),
526             name,
527         }
528     }
529 }
530
531 pub trait NestedAttributesExt {
532     /// Returns whether the attribute list contains a specific `Word`
533     fn has_word(self, word: &str) -> bool;
534 }
535
536 impl<I: IntoIterator<Item=ast::NestedMetaItem>> NestedAttributesExt for I {
537     fn has_word(self, word: &str) -> bool {
538         self.into_iter().any(|attr| attr.is_word() && attr.check_name(word))
539     }
540 }
541
542 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug, Default)]
543 pub struct Attributes {
544     pub doc_strings: Vec<String>,
545     pub other_attrs: Vec<ast::Attribute>,
546     pub cfg: Option<Rc<Cfg>>,
547     pub span: Option<syntax_pos::Span>,
548 }
549
550 impl Attributes {
551     /// Extracts the content from an attribute `#[doc(cfg(content))]`.
552     fn extract_cfg(mi: &ast::MetaItem) -> Option<&ast::MetaItem> {
553         use syntax::ast::NestedMetaItemKind::MetaItem;
554
555         if let ast::MetaItemKind::List(ref nmis) = mi.node {
556             if nmis.len() == 1 {
557                 if let MetaItem(ref cfg_mi) = nmis[0].node {
558                     if cfg_mi.check_name("cfg") {
559                         if let ast::MetaItemKind::List(ref cfg_nmis) = cfg_mi.node {
560                             if cfg_nmis.len() == 1 {
561                                 if let MetaItem(ref content_mi) = cfg_nmis[0].node {
562                                     return Some(content_mi);
563                                 }
564                             }
565                         }
566                     }
567                 }
568             }
569         }
570
571         None
572     }
573
574     pub fn from_ast(diagnostic: &::errors::Handler, attrs: &[ast::Attribute]) -> Attributes {
575         let mut doc_strings = vec![];
576         let mut sp = None;
577         let mut cfg = Cfg::True;
578
579         let other_attrs = attrs.iter().filter_map(|attr| {
580             attr.with_desugared_doc(|attr| {
581                 if attr.check_name("doc") {
582                     if let Some(mi) = attr.meta() {
583                         if let Some(value) = mi.value_str() {
584                             // Extracted #[doc = "..."]
585                             doc_strings.push(value.to_string());
586                             if sp.is_none() {
587                                 sp = Some(attr.span);
588                             }
589                             return None;
590                         } else if let Some(cfg_mi) = Attributes::extract_cfg(&mi) {
591                             // Extracted #[doc(cfg(...))]
592                             match Cfg::parse(cfg_mi) {
593                                 Ok(new_cfg) => cfg &= new_cfg,
594                                 Err(e) => diagnostic.span_err(e.span, e.msg),
595                             }
596                             return None;
597                         }
598                     }
599                 }
600                 Some(attr.clone())
601             })
602         }).collect();
603         Attributes {
604             doc_strings,
605             other_attrs,
606             cfg: if cfg == Cfg::True { None } else { Some(Rc::new(cfg)) },
607             span: sp,
608         }
609     }
610
611     /// Finds the `doc` attribute as a NameValue and returns the corresponding
612     /// value found.
613     pub fn doc_value<'a>(&'a self) -> Option<&'a str> {
614         self.doc_strings.first().map(|s| &s[..])
615     }
616 }
617
618 impl AttributesExt for Attributes {
619     fn lists<'a>(&'a self, name: &'a str) -> ListAttributesIter<'a> {
620         self.other_attrs.lists(name)
621     }
622 }
623
624 impl Clean<Attributes> for [ast::Attribute] {
625     fn clean(&self, cx: &DocContext) -> Attributes {
626         Attributes::from_ast(cx.sess().diagnostic(), self)
627     }
628 }
629
630 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
631 pub struct TyParam {
632     pub name: String,
633     pub did: DefId,
634     pub bounds: Vec<TyParamBound>,
635     pub default: Option<Type>,
636 }
637
638 impl Clean<TyParam> for hir::TyParam {
639     fn clean(&self, cx: &DocContext) -> TyParam {
640         TyParam {
641             name: self.name.clean(cx),
642             did: cx.tcx.hir.local_def_id(self.id),
643             bounds: self.bounds.clean(cx),
644             default: self.default.clean(cx),
645         }
646     }
647 }
648
649 impl<'tcx> Clean<TyParam> for ty::TypeParameterDef {
650     fn clean(&self, cx: &DocContext) -> TyParam {
651         cx.renderinfo.borrow_mut().external_typarams.insert(self.def_id, self.name.clean(cx));
652         TyParam {
653             name: self.name.clean(cx),
654             did: self.def_id,
655             bounds: vec![], // these are filled in from the where-clauses
656             default: if self.has_default {
657                 Some(cx.tcx.type_of(self.def_id).clean(cx))
658             } else {
659                 None
660             }
661         }
662     }
663 }
664
665 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
666 pub enum TyParamBound {
667     RegionBound(Lifetime),
668     TraitBound(PolyTrait, hir::TraitBoundModifier)
669 }
670
671 impl TyParamBound {
672     fn maybe_sized(cx: &DocContext) -> TyParamBound {
673         let did = cx.tcx.require_lang_item(lang_items::SizedTraitLangItem);
674         let empty = cx.tcx.intern_substs(&[]);
675         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
676             Some(did), false, vec![], empty);
677         inline::record_extern_fqn(cx, did, TypeKind::Trait);
678         TraitBound(PolyTrait {
679             trait_: ResolvedPath {
680                 path,
681                 typarams: None,
682                 did,
683                 is_generic: false,
684             },
685             lifetimes: vec![]
686         }, hir::TraitBoundModifier::Maybe)
687     }
688
689     fn is_sized_bound(&self, cx: &DocContext) -> bool {
690         use rustc::hir::TraitBoundModifier as TBM;
691         if let TyParamBound::TraitBound(PolyTrait { ref trait_, .. }, TBM::None) = *self {
692             if trait_.def_id() == cx.tcx.lang_items.sized_trait() {
693                 return true;
694             }
695         }
696         false
697     }
698 }
699
700 impl Clean<TyParamBound> for hir::TyParamBound {
701     fn clean(&self, cx: &DocContext) -> TyParamBound {
702         match *self {
703             hir::RegionTyParamBound(lt) => RegionBound(lt.clean(cx)),
704             hir::TraitTyParamBound(ref t, modifier) => TraitBound(t.clean(cx), modifier),
705         }
706     }
707 }
708
709 fn external_path_params(cx: &DocContext, trait_did: Option<DefId>, has_self: bool,
710                         bindings: Vec<TypeBinding>, substs: &Substs) -> PathParameters {
711     let lifetimes = substs.regions().filter_map(|v| v.clean(cx)).collect();
712     let types = substs.types().skip(has_self as usize).collect::<Vec<_>>();
713
714     match trait_did {
715         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
716         Some(did) if cx.tcx.lang_items.fn_trait_kind(did).is_some() => {
717             assert_eq!(types.len(), 1);
718             let inputs = match types[0].sty {
719                 ty::TyTuple(ref tys, _) => tys.iter().map(|t| t.clean(cx)).collect(),
720                 _ => {
721                     return PathParameters::AngleBracketed {
722                         lifetimes,
723                         types: types.clean(cx),
724                         bindings,
725                     }
726                 }
727             };
728             let output = None;
729             // FIXME(#20299) return type comes from a projection now
730             // match types[1].sty {
731             //     ty::TyTuple(ref v, _) if v.is_empty() => None, // -> ()
732             //     _ => Some(types[1].clean(cx))
733             // };
734             PathParameters::Parenthesized {
735                 inputs,
736                 output,
737             }
738         },
739         _ => {
740             PathParameters::AngleBracketed {
741                 lifetimes,
742                 types: types.clean(cx),
743                 bindings,
744             }
745         }
746     }
747 }
748
749 // trait_did should be set to a trait's DefId if called on a TraitRef, in order to sugar
750 // from Fn<(A, B,), C> to Fn(A, B) -> C
751 fn external_path(cx: &DocContext, name: &str, trait_did: Option<DefId>, has_self: bool,
752                  bindings: Vec<TypeBinding>, substs: &Substs) -> Path {
753     Path {
754         global: false,
755         def: Def::Err,
756         segments: vec![PathSegment {
757             name: name.to_string(),
758             params: external_path_params(cx, trait_did, has_self, bindings, substs)
759         }],
760     }
761 }
762
763 impl<'tcx> Clean<TyParamBound> for ty::TraitRef<'tcx> {
764     fn clean(&self, cx: &DocContext) -> TyParamBound {
765         inline::record_extern_fqn(cx, self.def_id, TypeKind::Trait);
766         let path = external_path(cx, &cx.tcx.item_name(self.def_id).as_str(),
767                                  Some(self.def_id), true, vec![], self.substs);
768
769         debug!("ty::TraitRef\n  subst: {:?}\n", self.substs);
770
771         // collect any late bound regions
772         let mut late_bounds = vec![];
773         for ty_s in self.input_types().skip(1) {
774             if let ty::TyTuple(ts, _) = ty_s.sty {
775                 for &ty_s in ts {
776                     if let ty::TyRef(ref reg, _) = ty_s.sty {
777                         if let &ty::RegionKind::ReLateBound(..) = *reg {
778                             debug!("  hit an ReLateBound {:?}", reg);
779                             if let Some(lt) = reg.clean(cx) {
780                                 late_bounds.push(lt);
781                             }
782                         }
783                     }
784                 }
785             }
786         }
787
788         TraitBound(
789             PolyTrait {
790                 trait_: ResolvedPath {
791                     path,
792                     typarams: None,
793                     did: self.def_id,
794                     is_generic: false,
795                 },
796                 lifetimes: late_bounds,
797             },
798             hir::TraitBoundModifier::None
799         )
800     }
801 }
802
803 impl<'tcx> Clean<Option<Vec<TyParamBound>>> for Substs<'tcx> {
804     fn clean(&self, cx: &DocContext) -> Option<Vec<TyParamBound>> {
805         let mut v = Vec::new();
806         v.extend(self.regions().filter_map(|r| r.clean(cx))
807                      .map(RegionBound));
808         v.extend(self.types().map(|t| TraitBound(PolyTrait {
809             trait_: t.clean(cx),
810             lifetimes: vec![]
811         }, hir::TraitBoundModifier::None)));
812         if !v.is_empty() {Some(v)} else {None}
813     }
814 }
815
816 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
817 pub struct Lifetime(String);
818
819 impl Lifetime {
820     pub fn get_ref<'a>(&'a self) -> &'a str {
821         let Lifetime(ref s) = *self;
822         let s: &'a str = s;
823         s
824     }
825
826     pub fn statik() -> Lifetime {
827         Lifetime("'static".to_string())
828     }
829 }
830
831 impl Clean<Lifetime> for hir::Lifetime {
832     fn clean(&self, cx: &DocContext) -> Lifetime {
833         let hir_id = cx.tcx.hir.node_to_hir_id(self.id);
834         let def = cx.tcx.named_region(hir_id);
835         match def {
836             Some(rl::Region::EarlyBound(_, node_id)) |
837             Some(rl::Region::LateBound(_, node_id)) |
838             Some(rl::Region::Free(_, node_id)) => {
839                 if let Some(lt) = cx.lt_substs.borrow().get(&node_id).cloned() {
840                     return lt;
841                 }
842             }
843             _ => {}
844         }
845         Lifetime(self.name.to_string())
846     }
847 }
848
849 impl Clean<Lifetime> for hir::LifetimeDef {
850     fn clean(&self, _: &DocContext) -> Lifetime {
851         if self.bounds.len() > 0 {
852             let mut s = format!("{}: {}",
853                                 self.lifetime.name.to_string(),
854                                 self.bounds[0].name.to_string());
855             for bound in self.bounds.iter().skip(1) {
856                 s.push_str(&format!(" + {}", bound.name.to_string()));
857             }
858             Lifetime(s)
859         } else {
860             Lifetime(self.lifetime.name.to_string())
861         }
862     }
863 }
864
865 impl Clean<Lifetime> for ty::RegionParameterDef {
866     fn clean(&self, _: &DocContext) -> Lifetime {
867         Lifetime(self.name.to_string())
868     }
869 }
870
871 impl Clean<Option<Lifetime>> for ty::RegionKind {
872     fn clean(&self, cx: &DocContext) -> Option<Lifetime> {
873         match *self {
874             ty::ReStatic => Some(Lifetime::statik()),
875             ty::ReLateBound(_, ty::BrNamed(_, name)) => Some(Lifetime(name.to_string())),
876             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
877
878             ty::ReLateBound(..) |
879             ty::ReFree(..) |
880             ty::ReScope(..) |
881             ty::ReVar(..) |
882             ty::ReSkolemized(..) |
883             ty::ReEmpty |
884             ty::ReErased => None
885         }
886     }
887 }
888
889 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
890 pub enum WherePredicate {
891     BoundPredicate { ty: Type, bounds: Vec<TyParamBound> },
892     RegionPredicate { lifetime: Lifetime, bounds: Vec<Lifetime>},
893     EqPredicate { lhs: Type, rhs: Type },
894 }
895
896 impl Clean<WherePredicate> for hir::WherePredicate {
897     fn clean(&self, cx: &DocContext) -> WherePredicate {
898         match *self {
899             hir::WherePredicate::BoundPredicate(ref wbp) => {
900                 WherePredicate::BoundPredicate {
901                     ty: wbp.bounded_ty.clean(cx),
902                     bounds: wbp.bounds.clean(cx)
903                 }
904             }
905
906             hir::WherePredicate::RegionPredicate(ref wrp) => {
907                 WherePredicate::RegionPredicate {
908                     lifetime: wrp.lifetime.clean(cx),
909                     bounds: wrp.bounds.clean(cx)
910                 }
911             }
912
913             hir::WherePredicate::EqPredicate(ref wrp) => {
914                 WherePredicate::EqPredicate {
915                     lhs: wrp.lhs_ty.clean(cx),
916                     rhs: wrp.rhs_ty.clean(cx)
917                 }
918             }
919         }
920     }
921 }
922
923 impl<'a> Clean<WherePredicate> for ty::Predicate<'a> {
924     fn clean(&self, cx: &DocContext) -> WherePredicate {
925         use rustc::ty::Predicate;
926
927         match *self {
928             Predicate::Trait(ref pred) => pred.clean(cx),
929             Predicate::Equate(ref pred) => pred.clean(cx),
930             Predicate::Subtype(ref pred) => pred.clean(cx),
931             Predicate::RegionOutlives(ref pred) => pred.clean(cx),
932             Predicate::TypeOutlives(ref pred) => pred.clean(cx),
933             Predicate::Projection(ref pred) => pred.clean(cx),
934             Predicate::WellFormed(_) => panic!("not user writable"),
935             Predicate::ObjectSafe(_) => panic!("not user writable"),
936             Predicate::ClosureKind(..) => panic!("not user writable"),
937         }
938     }
939 }
940
941 impl<'a> Clean<WherePredicate> for ty::TraitPredicate<'a> {
942     fn clean(&self, cx: &DocContext) -> WherePredicate {
943         WherePredicate::BoundPredicate {
944             ty: self.trait_ref.self_ty().clean(cx),
945             bounds: vec![self.trait_ref.clean(cx)]
946         }
947     }
948 }
949
950 impl<'tcx> Clean<WherePredicate> for ty::EquatePredicate<'tcx> {
951     fn clean(&self, cx: &DocContext) -> WherePredicate {
952         let ty::EquatePredicate(ref lhs, ref rhs) = *self;
953         WherePredicate::EqPredicate {
954             lhs: lhs.clean(cx),
955             rhs: rhs.clean(cx)
956         }
957     }
958 }
959
960 impl<'tcx> Clean<WherePredicate> for ty::SubtypePredicate<'tcx> {
961     fn clean(&self, _cx: &DocContext) -> WherePredicate {
962         panic!("subtype predicates are an internal rustc artifact \
963                 and should not be seen by rustdoc")
964     }
965 }
966
967 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<ty::Region<'tcx>, ty::Region<'tcx>> {
968     fn clean(&self, cx: &DocContext) -> WherePredicate {
969         let ty::OutlivesPredicate(ref a, ref b) = *self;
970         WherePredicate::RegionPredicate {
971             lifetime: a.clean(cx).unwrap(),
972             bounds: vec![b.clean(cx).unwrap()]
973         }
974     }
975 }
976
977 impl<'tcx> Clean<WherePredicate> for ty::OutlivesPredicate<ty::Ty<'tcx>, ty::Region<'tcx>> {
978     fn clean(&self, cx: &DocContext) -> WherePredicate {
979         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
980
981         WherePredicate::BoundPredicate {
982             ty: ty.clean(cx),
983             bounds: vec![TyParamBound::RegionBound(lt.clean(cx).unwrap())]
984         }
985     }
986 }
987
988 impl<'tcx> Clean<WherePredicate> for ty::ProjectionPredicate<'tcx> {
989     fn clean(&self, cx: &DocContext) -> WherePredicate {
990         WherePredicate::EqPredicate {
991             lhs: self.projection_ty.clean(cx),
992             rhs: self.ty.clean(cx)
993         }
994     }
995 }
996
997 impl<'tcx> Clean<Type> for ty::ProjectionTy<'tcx> {
998     fn clean(&self, cx: &DocContext) -> Type {
999         let trait_ = match self.trait_ref(cx.tcx).clean(cx) {
1000             TyParamBound::TraitBound(t, _) => t.trait_,
1001             TyParamBound::RegionBound(_) => {
1002                 panic!("cleaning a trait got a region")
1003             }
1004         };
1005         Type::QPath {
1006             name: cx.tcx.associated_item(self.item_def_id).name.clean(cx),
1007             self_type: box self.self_ty().clean(cx),
1008             trait_: box trait_
1009         }
1010     }
1011 }
1012
1013 // maybe use a Generic enum and use Vec<Generic>?
1014 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1015 pub struct Generics {
1016     pub lifetimes: Vec<Lifetime>,
1017     pub type_params: Vec<TyParam>,
1018     pub where_predicates: Vec<WherePredicate>
1019 }
1020
1021 impl Clean<Generics> for hir::Generics {
1022     fn clean(&self, cx: &DocContext) -> Generics {
1023         Generics {
1024             lifetimes: self.lifetimes.clean(cx),
1025             type_params: self.ty_params.clean(cx),
1026             where_predicates: self.where_clause.predicates.clean(cx)
1027         }
1028     }
1029 }
1030
1031 impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics,
1032                                     &'a ty::GenericPredicates<'tcx>) {
1033     fn clean(&self, cx: &DocContext) -> Generics {
1034         use self::WherePredicate as WP;
1035
1036         let (gens, preds) = *self;
1037
1038         // Bounds in the type_params and lifetimes fields are repeated in the
1039         // predicates field (see rustc_typeck::collect::ty_generics), so remove
1040         // them.
1041         let stripped_typarams = gens.types.iter().filter_map(|tp| {
1042             if tp.name == keywords::SelfType.name() {
1043                 assert_eq!(tp.index, 0);
1044                 None
1045             } else {
1046                 Some(tp.clean(cx))
1047             }
1048         }).collect::<Vec<_>>();
1049
1050         let mut where_predicates = preds.predicates.to_vec().clean(cx);
1051
1052         // Type parameters and have a Sized bound by default unless removed with
1053         // ?Sized.  Scan through the predicates and mark any type parameter with
1054         // a Sized bound, removing the bounds as we find them.
1055         //
1056         // Note that associated types also have a sized bound by default, but we
1057         // don't actually know the set of associated types right here so that's
1058         // handled in cleaning associated types
1059         let mut sized_params = FxHashSet();
1060         where_predicates.retain(|pred| {
1061             match *pred {
1062                 WP::BoundPredicate { ty: Generic(ref g), ref bounds } => {
1063                     if bounds.iter().any(|b| b.is_sized_bound(cx)) {
1064                         sized_params.insert(g.clone());
1065                         false
1066                     } else {
1067                         true
1068                     }
1069                 }
1070                 _ => true,
1071             }
1072         });
1073
1074         // Run through the type parameters again and insert a ?Sized
1075         // unbound for any we didn't find to be Sized.
1076         for tp in &stripped_typarams {
1077             if !sized_params.contains(&tp.name) {
1078                 where_predicates.push(WP::BoundPredicate {
1079                     ty: Type::Generic(tp.name.clone()),
1080                     bounds: vec![TyParamBound::maybe_sized(cx)],
1081                 })
1082             }
1083         }
1084
1085         // It would be nice to collect all of the bounds on a type and recombine
1086         // them if possible, to avoid e.g. `where T: Foo, T: Bar, T: Sized, T: 'a`
1087         // and instead see `where T: Foo + Bar + Sized + 'a`
1088
1089         Generics {
1090             type_params: simplify::ty_params(stripped_typarams),
1091             lifetimes: gens.regions.clean(cx),
1092             where_predicates: simplify::where_clauses(cx, where_predicates),
1093         }
1094     }
1095 }
1096
1097 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1098 pub struct Method {
1099     pub generics: Generics,
1100     pub unsafety: hir::Unsafety,
1101     pub constness: hir::Constness,
1102     pub decl: FnDecl,
1103     pub abi: Abi,
1104 }
1105
1106 impl<'a> Clean<Method> for (&'a hir::MethodSig, hir::BodyId) {
1107     fn clean(&self, cx: &DocContext) -> Method {
1108         Method {
1109             generics: self.0.generics.clean(cx),
1110             unsafety: self.0.unsafety,
1111             constness: self.0.constness,
1112             decl: (&*self.0.decl, self.1).clean(cx),
1113             abi: self.0.abi
1114         }
1115     }
1116 }
1117
1118 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1119 pub struct TyMethod {
1120     pub unsafety: hir::Unsafety,
1121     pub decl: FnDecl,
1122     pub generics: Generics,
1123     pub abi: Abi,
1124 }
1125
1126 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1127 pub struct Function {
1128     pub decl: FnDecl,
1129     pub generics: Generics,
1130     pub unsafety: hir::Unsafety,
1131     pub constness: hir::Constness,
1132     pub abi: Abi,
1133 }
1134
1135 impl Clean<Item> for doctree::Function {
1136     fn clean(&self, cx: &DocContext) -> Item {
1137         Item {
1138             name: Some(self.name.clean(cx)),
1139             attrs: self.attrs.clean(cx),
1140             source: self.whence.clean(cx),
1141             visibility: self.vis.clean(cx),
1142             stability: self.stab.clean(cx),
1143             deprecation: self.depr.clean(cx),
1144             def_id: cx.tcx.hir.local_def_id(self.id),
1145             inner: FunctionItem(Function {
1146                 decl: (&self.decl, self.body).clean(cx),
1147                 generics: self.generics.clean(cx),
1148                 unsafety: self.unsafety,
1149                 constness: self.constness,
1150                 abi: self.abi,
1151             }),
1152         }
1153     }
1154 }
1155
1156 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1157 pub struct FnDecl {
1158     pub inputs: Arguments,
1159     pub output: FunctionRetTy,
1160     pub variadic: bool,
1161     pub attrs: Attributes,
1162 }
1163
1164 impl FnDecl {
1165     pub fn has_self(&self) -> bool {
1166         self.inputs.values.len() > 0 && self.inputs.values[0].name == "self"
1167     }
1168
1169     pub fn self_type(&self) -> Option<SelfTy> {
1170         self.inputs.values.get(0).and_then(|v| v.to_self())
1171     }
1172 }
1173
1174 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1175 pub struct Arguments {
1176     pub values: Vec<Argument>,
1177 }
1178
1179 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], &'a [Spanned<ast::Name>]) {
1180     fn clean(&self, cx: &DocContext) -> Arguments {
1181         Arguments {
1182             values: self.0.iter().enumerate().map(|(i, ty)| {
1183                 let mut name = self.1.get(i).map(|n| n.node.to_string())
1184                                             .unwrap_or(String::new());
1185                 if name.is_empty() {
1186                     name = "_".to_string();
1187                 }
1188                 Argument {
1189                     name,
1190                     type_: ty.clean(cx),
1191                 }
1192             }).collect()
1193         }
1194     }
1195 }
1196
1197 impl<'a> Clean<Arguments> for (&'a [P<hir::Ty>], hir::BodyId) {
1198     fn clean(&self, cx: &DocContext) -> Arguments {
1199         let body = cx.tcx.hir.body(self.1);
1200
1201         Arguments {
1202             values: self.0.iter().enumerate().map(|(i, ty)| {
1203                 Argument {
1204                     name: name_from_pat(&body.arguments[i].pat),
1205                     type_: ty.clean(cx),
1206                 }
1207             }).collect()
1208         }
1209     }
1210 }
1211
1212 impl<'a, A: Copy> Clean<FnDecl> for (&'a hir::FnDecl, A)
1213     where (&'a [P<hir::Ty>], A): Clean<Arguments>
1214 {
1215     fn clean(&self, cx: &DocContext) -> FnDecl {
1216         FnDecl {
1217             inputs: (&self.0.inputs[..], self.1).clean(cx),
1218             output: self.0.output.clean(cx),
1219             variadic: self.0.variadic,
1220             attrs: Attributes::default()
1221         }
1222     }
1223 }
1224
1225 impl<'a, 'tcx> Clean<FnDecl> for (DefId, ty::PolyFnSig<'tcx>) {
1226     fn clean(&self, cx: &DocContext) -> FnDecl {
1227         let (did, sig) = *self;
1228         let mut names = if cx.tcx.hir.as_local_node_id(did).is_some() {
1229             vec![].into_iter()
1230         } else {
1231             cx.tcx.fn_arg_names(did).into_iter()
1232         }.peekable();
1233         FnDecl {
1234             output: Return(sig.skip_binder().output().clean(cx)),
1235             attrs: Attributes::default(),
1236             variadic: sig.skip_binder().variadic,
1237             inputs: Arguments {
1238                 values: sig.skip_binder().inputs().iter().map(|t| {
1239                     Argument {
1240                         type_: t.clean(cx),
1241                         name: names.next().map_or("".to_string(), |name| name.to_string()),
1242                     }
1243                 }).collect(),
1244             },
1245         }
1246     }
1247 }
1248
1249 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1250 pub struct Argument {
1251     pub type_: Type,
1252     pub name: String,
1253 }
1254
1255 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1256 pub enum SelfTy {
1257     SelfValue,
1258     SelfBorrowed(Option<Lifetime>, Mutability),
1259     SelfExplicit(Type),
1260 }
1261
1262 impl Argument {
1263     pub fn to_self(&self) -> Option<SelfTy> {
1264         if self.name != "self" {
1265             return None;
1266         }
1267         if self.type_.is_self_type() {
1268             return Some(SelfValue);
1269         }
1270         match self.type_ {
1271             BorrowedRef{ref lifetime, mutability, ref type_} if type_.is_self_type() => {
1272                 Some(SelfBorrowed(lifetime.clone(), mutability))
1273             }
1274             _ => Some(SelfExplicit(self.type_.clone()))
1275         }
1276     }
1277 }
1278
1279 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1280 pub enum FunctionRetTy {
1281     Return(Type),
1282     DefaultReturn,
1283 }
1284
1285 impl Clean<FunctionRetTy> for hir::FunctionRetTy {
1286     fn clean(&self, cx: &DocContext) -> FunctionRetTy {
1287         match *self {
1288             hir::Return(ref typ) => Return(typ.clean(cx)),
1289             hir::DefaultReturn(..) => DefaultReturn,
1290         }
1291     }
1292 }
1293
1294 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
1295 pub struct Trait {
1296     pub unsafety: hir::Unsafety,
1297     pub items: Vec<Item>,
1298     pub generics: Generics,
1299     pub bounds: Vec<TyParamBound>,
1300 }
1301
1302 impl Clean<Item> for doctree::Trait {
1303     fn clean(&self, cx: &DocContext) -> Item {
1304         Item {
1305             name: Some(self.name.clean(cx)),
1306             attrs: self.attrs.clean(cx),
1307             source: self.whence.clean(cx),
1308             def_id: cx.tcx.hir.local_def_id(self.id),
1309             visibility: self.vis.clean(cx),
1310             stability: self.stab.clean(cx),
1311             deprecation: self.depr.clean(cx),
1312             inner: TraitItem(Trait {
1313                 unsafety: self.unsafety,
1314                 items: self.items.clean(cx),
1315                 generics: self.generics.clean(cx),
1316                 bounds: self.bounds.clean(cx),
1317             }),
1318         }
1319     }
1320 }
1321
1322 impl Clean<Type> for hir::TraitRef {
1323     fn clean(&self, cx: &DocContext) -> Type {
1324         resolve_type(cx, self.path.clean(cx), self.ref_id)
1325     }
1326 }
1327
1328 impl Clean<PolyTrait> for hir::PolyTraitRef {
1329     fn clean(&self, cx: &DocContext) -> PolyTrait {
1330         PolyTrait {
1331             trait_: self.trait_ref.clean(cx),
1332             lifetimes: self.bound_lifetimes.clean(cx)
1333         }
1334     }
1335 }
1336
1337 impl Clean<Item> for hir::TraitItem {
1338     fn clean(&self, cx: &DocContext) -> Item {
1339         let inner = match self.node {
1340             hir::TraitItemKind::Const(ref ty, default) => {
1341                 AssociatedConstItem(ty.clean(cx),
1342                                     default.map(|e| print_const_expr(cx, e)))
1343             }
1344             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Provided(body)) => {
1345                 MethodItem((sig, body).clean(cx))
1346             }
1347             hir::TraitItemKind::Method(ref sig, hir::TraitMethod::Required(ref names)) => {
1348                 TyMethodItem(TyMethod {
1349                     unsafety: sig.unsafety.clone(),
1350                     decl: (&*sig.decl, &names[..]).clean(cx),
1351                     generics: sig.generics.clean(cx),
1352                     abi: sig.abi
1353                 })
1354             }
1355             hir::TraitItemKind::Type(ref bounds, ref default) => {
1356                 AssociatedTypeItem(bounds.clean(cx), default.clean(cx))
1357             }
1358         };
1359         Item {
1360             name: Some(self.name.clean(cx)),
1361             attrs: self.attrs.clean(cx),
1362             source: self.span.clean(cx),
1363             def_id: cx.tcx.hir.local_def_id(self.id),
1364             visibility: None,
1365             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
1366             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
1367             inner,
1368         }
1369     }
1370 }
1371
1372 impl Clean<Item> for hir::ImplItem {
1373     fn clean(&self, cx: &DocContext) -> Item {
1374         let inner = match self.node {
1375             hir::ImplItemKind::Const(ref ty, expr) => {
1376                 AssociatedConstItem(ty.clean(cx),
1377                                     Some(print_const_expr(cx, expr)))
1378             }
1379             hir::ImplItemKind::Method(ref sig, body) => {
1380                 MethodItem((sig, body).clean(cx))
1381             }
1382             hir::ImplItemKind::Type(ref ty) => TypedefItem(Typedef {
1383                 type_: ty.clean(cx),
1384                 generics: Generics {
1385                     lifetimes: Vec::new(),
1386                     type_params: Vec::new(),
1387                     where_predicates: Vec::new()
1388                 },
1389             }, true),
1390         };
1391         Item {
1392             name: Some(self.name.clean(cx)),
1393             source: self.span.clean(cx),
1394             attrs: self.attrs.clean(cx),
1395             def_id: cx.tcx.hir.local_def_id(self.id),
1396             visibility: self.vis.clean(cx),
1397             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
1398             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
1399             inner,
1400         }
1401     }
1402 }
1403
1404 impl<'tcx> Clean<Item> for ty::AssociatedItem {
1405     fn clean(&self, cx: &DocContext) -> Item {
1406         let inner = match self.kind {
1407             ty::AssociatedKind::Const => {
1408                 let ty = cx.tcx.type_of(self.def_id);
1409                 AssociatedConstItem(ty.clean(cx), None)
1410             }
1411             ty::AssociatedKind::Method => {
1412                 let generics = (cx.tcx.generics_of(self.def_id),
1413                                 &cx.tcx.predicates_of(self.def_id)).clean(cx);
1414                 let sig = cx.tcx.fn_sig(self.def_id);
1415                 let mut decl = (self.def_id, sig).clean(cx);
1416
1417                 if self.method_has_self_argument {
1418                     let self_ty = match self.container {
1419                         ty::ImplContainer(def_id) => {
1420                             cx.tcx.type_of(def_id)
1421                         }
1422                         ty::TraitContainer(_) => cx.tcx.mk_self_type()
1423                     };
1424                     let self_arg_ty = *sig.input(0).skip_binder();
1425                     if self_arg_ty == self_ty {
1426                         decl.inputs.values[0].type_ = Generic(String::from("Self"));
1427                     } else if let ty::TyRef(_, mt) = self_arg_ty.sty {
1428                         if mt.ty == self_ty {
1429                             match decl.inputs.values[0].type_ {
1430                                 BorrowedRef{ref mut type_, ..} => {
1431                                     **type_ = Generic(String::from("Self"))
1432                                 }
1433                                 _ => unreachable!(),
1434                             }
1435                         }
1436                     }
1437                 }
1438
1439                 let provided = match self.container {
1440                     ty::ImplContainer(_) => false,
1441                     ty::TraitContainer(_) => self.defaultness.has_value()
1442                 };
1443                 if provided {
1444                     MethodItem(Method {
1445                         unsafety: sig.unsafety(),
1446                         generics,
1447                         decl,
1448                         abi: sig.abi(),
1449
1450                         // trait methods cannot (currently, at least) be const
1451                         constness: hir::Constness::NotConst,
1452                     })
1453                 } else {
1454                     TyMethodItem(TyMethod {
1455                         unsafety: sig.unsafety(),
1456                         generics,
1457                         decl,
1458                         abi: sig.abi(),
1459                     })
1460                 }
1461             }
1462             ty::AssociatedKind::Type => {
1463                 let my_name = self.name.clean(cx);
1464
1465                 let mut bounds = if let ty::TraitContainer(did) = self.container {
1466                     // When loading a cross-crate associated type, the bounds for this type
1467                     // are actually located on the trait/impl itself, so we need to load
1468                     // all of the generics from there and then look for bounds that are
1469                     // applied to this associated type in question.
1470                     let predicates = cx.tcx.predicates_of(did);
1471                     let generics = (cx.tcx.generics_of(did), &predicates).clean(cx);
1472                     generics.where_predicates.iter().filter_map(|pred| {
1473                         let (name, self_type, trait_, bounds) = match *pred {
1474                             WherePredicate::BoundPredicate {
1475                                 ty: QPath { ref name, ref self_type, ref trait_ },
1476                                 ref bounds
1477                             } => (name, self_type, trait_, bounds),
1478                             _ => return None,
1479                         };
1480                         if *name != my_name { return None }
1481                         match **trait_ {
1482                             ResolvedPath { did, .. } if did == self.container.id() => {}
1483                             _ => return None,
1484                         }
1485                         match **self_type {
1486                             Generic(ref s) if *s == "Self" => {}
1487                             _ => return None,
1488                         }
1489                         Some(bounds)
1490                     }).flat_map(|i| i.iter().cloned()).collect::<Vec<_>>()
1491                 } else {
1492                     vec![]
1493                 };
1494
1495                 // Our Sized/?Sized bound didn't get handled when creating the generics
1496                 // because we didn't actually get our whole set of bounds until just now
1497                 // (some of them may have come from the trait). If we do have a sized
1498                 // bound, we remove it, and if we don't then we add the `?Sized` bound
1499                 // at the end.
1500                 match bounds.iter().position(|b| b.is_sized_bound(cx)) {
1501                     Some(i) => { bounds.remove(i); }
1502                     None => bounds.push(TyParamBound::maybe_sized(cx)),
1503                 }
1504
1505                 let ty = if self.defaultness.has_value() {
1506                     Some(cx.tcx.type_of(self.def_id))
1507                 } else {
1508                     None
1509                 };
1510
1511                 AssociatedTypeItem(bounds, ty.clean(cx))
1512             }
1513         };
1514
1515         Item {
1516             name: Some(self.name.clean(cx)),
1517             visibility: Some(Inherited),
1518             stability: get_stability(cx, self.def_id),
1519             deprecation: get_deprecation(cx, self.def_id),
1520             def_id: self.def_id,
1521             attrs: inline::load_attrs(cx, self.def_id),
1522             source: cx.tcx.def_span(self.def_id).clean(cx),
1523             inner,
1524         }
1525     }
1526 }
1527
1528 /// A trait reference, which may have higher ranked lifetimes.
1529 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1530 pub struct PolyTrait {
1531     pub trait_: Type,
1532     pub lifetimes: Vec<Lifetime>
1533 }
1534
1535 /// A representation of a Type suitable for hyperlinking purposes. Ideally one can get the original
1536 /// type out of the AST/TyCtxt given one of these, if more information is needed. Most importantly
1537 /// it does not preserve mutability or boxes.
1538 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
1539 pub enum Type {
1540     /// structs/enums/traits (most that'd be an hir::TyPath)
1541     ResolvedPath {
1542         path: Path,
1543         typarams: Option<Vec<TyParamBound>>,
1544         did: DefId,
1545         /// true if is a `T::Name` path for associated types
1546         is_generic: bool,
1547     },
1548     /// For parameterized types, so the consumer of the JSON don't go
1549     /// looking for types which don't exist anywhere.
1550     Generic(String),
1551     /// Primitives are the fixed-size numeric types (plus int/usize/float), char,
1552     /// arrays, slices, and tuples.
1553     Primitive(PrimitiveType),
1554     /// extern "ABI" fn
1555     BareFunction(Box<BareFunctionDecl>),
1556     Tuple(Vec<Type>),
1557     Slice(Box<Type>),
1558     Array(Box<Type>, usize),
1559     Never,
1560     Unique(Box<Type>),
1561     RawPointer(Mutability, Box<Type>),
1562     BorrowedRef {
1563         lifetime: Option<Lifetime>,
1564         mutability: Mutability,
1565         type_: Box<Type>,
1566     },
1567
1568     // <Type as Trait>::Name
1569     QPath {
1570         name: String,
1571         self_type: Box<Type>,
1572         trait_: Box<Type>
1573     },
1574
1575     // _
1576     Infer,
1577
1578     // impl TraitA+TraitB
1579     ImplTrait(Vec<TyParamBound>),
1580 }
1581
1582 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Copy, Debug)]
1583 pub enum PrimitiveType {
1584     Isize, I8, I16, I32, I64, I128,
1585     Usize, U8, U16, U32, U64, U128,
1586     F32, F64,
1587     Char,
1588     Bool,
1589     Str,
1590     Slice,
1591     Array,
1592     Tuple,
1593     RawPointer,
1594     Reference,
1595     Fn,
1596 }
1597
1598 #[derive(Clone, RustcEncodable, RustcDecodable, Copy, Debug)]
1599 pub enum TypeKind {
1600     Enum,
1601     Function,
1602     Module,
1603     Const,
1604     Static,
1605     Struct,
1606     Union,
1607     Trait,
1608     Variant,
1609     Typedef,
1610 }
1611
1612 pub trait GetDefId {
1613     fn def_id(&self) -> Option<DefId>;
1614 }
1615
1616 impl<T: GetDefId> GetDefId for Option<T> {
1617     fn def_id(&self) -> Option<DefId> {
1618         self.as_ref().and_then(|d| d.def_id())
1619     }
1620 }
1621
1622 impl Type {
1623     pub fn primitive_type(&self) -> Option<PrimitiveType> {
1624         match *self {
1625             Primitive(p) | BorrowedRef { type_: box Primitive(p), ..} => Some(p),
1626             Slice(..) | BorrowedRef { type_: box Slice(..), .. } => Some(PrimitiveType::Slice),
1627             Array(..) | BorrowedRef { type_: box Array(..), .. } => Some(PrimitiveType::Array),
1628             Tuple(..) => Some(PrimitiveType::Tuple),
1629             RawPointer(..) => Some(PrimitiveType::RawPointer),
1630             BorrowedRef { type_: box Generic(..), .. } => Some(PrimitiveType::Reference),
1631             BareFunction(..) => Some(PrimitiveType::Fn),
1632             _ => None,
1633         }
1634     }
1635
1636     pub fn is_generic(&self) -> bool {
1637         match *self {
1638             ResolvedPath { is_generic, .. } => is_generic,
1639             _ => false,
1640         }
1641     }
1642
1643     pub fn is_self_type(&self) -> bool {
1644         match *self {
1645             Generic(ref name) => name == "Self",
1646             _ => false
1647         }
1648     }
1649 }
1650
1651 impl GetDefId for Type {
1652     fn def_id(&self) -> Option<DefId> {
1653         match *self {
1654             ResolvedPath { did, .. } => Some(did),
1655             _ => None,
1656         }
1657     }
1658 }
1659
1660 impl PrimitiveType {
1661     fn from_str(s: &str) -> Option<PrimitiveType> {
1662         match s {
1663             "isize" => Some(PrimitiveType::Isize),
1664             "i8" => Some(PrimitiveType::I8),
1665             "i16" => Some(PrimitiveType::I16),
1666             "i32" => Some(PrimitiveType::I32),
1667             "i64" => Some(PrimitiveType::I64),
1668             "i128" => Some(PrimitiveType::I128),
1669             "usize" => Some(PrimitiveType::Usize),
1670             "u8" => Some(PrimitiveType::U8),
1671             "u16" => Some(PrimitiveType::U16),
1672             "u32" => Some(PrimitiveType::U32),
1673             "u64" => Some(PrimitiveType::U64),
1674             "u128" => Some(PrimitiveType::U128),
1675             "bool" => Some(PrimitiveType::Bool),
1676             "char" => Some(PrimitiveType::Char),
1677             "str" => Some(PrimitiveType::Str),
1678             "f32" => Some(PrimitiveType::F32),
1679             "f64" => Some(PrimitiveType::F64),
1680             "array" => Some(PrimitiveType::Array),
1681             "slice" => Some(PrimitiveType::Slice),
1682             "tuple" => Some(PrimitiveType::Tuple),
1683             "pointer" => Some(PrimitiveType::RawPointer),
1684             "reference" => Some(PrimitiveType::Reference),
1685             "fn" => Some(PrimitiveType::Fn),
1686             _ => None,
1687         }
1688     }
1689
1690     pub fn as_str(&self) -> &'static str {
1691         use self::PrimitiveType::*;
1692         match *self {
1693             Isize => "isize",
1694             I8 => "i8",
1695             I16 => "i16",
1696             I32 => "i32",
1697             I64 => "i64",
1698             I128 => "i128",
1699             Usize => "usize",
1700             U8 => "u8",
1701             U16 => "u16",
1702             U32 => "u32",
1703             U64 => "u64",
1704             U128 => "u128",
1705             F32 => "f32",
1706             F64 => "f64",
1707             Str => "str",
1708             Bool => "bool",
1709             Char => "char",
1710             Array => "array",
1711             Slice => "slice",
1712             Tuple => "tuple",
1713             RawPointer => "pointer",
1714             Reference => "reference",
1715             Fn => "fn",
1716         }
1717     }
1718
1719     pub fn to_url_str(&self) -> &'static str {
1720         self.as_str()
1721     }
1722 }
1723
1724 impl From<ast::IntTy> for PrimitiveType {
1725     fn from(int_ty: ast::IntTy) -> PrimitiveType {
1726         match int_ty {
1727             ast::IntTy::Is => PrimitiveType::Isize,
1728             ast::IntTy::I8 => PrimitiveType::I8,
1729             ast::IntTy::I16 => PrimitiveType::I16,
1730             ast::IntTy::I32 => PrimitiveType::I32,
1731             ast::IntTy::I64 => PrimitiveType::I64,
1732             ast::IntTy::I128 => PrimitiveType::I128,
1733         }
1734     }
1735 }
1736
1737 impl From<ast::UintTy> for PrimitiveType {
1738     fn from(uint_ty: ast::UintTy) -> PrimitiveType {
1739         match uint_ty {
1740             ast::UintTy::Us => PrimitiveType::Usize,
1741             ast::UintTy::U8 => PrimitiveType::U8,
1742             ast::UintTy::U16 => PrimitiveType::U16,
1743             ast::UintTy::U32 => PrimitiveType::U32,
1744             ast::UintTy::U64 => PrimitiveType::U64,
1745             ast::UintTy::U128 => PrimitiveType::U128,
1746         }
1747     }
1748 }
1749
1750 impl From<ast::FloatTy> for PrimitiveType {
1751     fn from(float_ty: ast::FloatTy) -> PrimitiveType {
1752         match float_ty {
1753             ast::FloatTy::F32 => PrimitiveType::F32,
1754             ast::FloatTy::F64 => PrimitiveType::F64,
1755         }
1756     }
1757 }
1758
1759 impl Clean<Type> for hir::Ty {
1760     fn clean(&self, cx: &DocContext) -> Type {
1761         use rustc::hir::*;
1762         match self.node {
1763             TyNever => Never,
1764             TyPtr(ref m) => RawPointer(m.mutbl.clean(cx), box m.ty.clean(cx)),
1765             TyRptr(ref l, ref m) => {
1766                 let lifetime = if l.is_elided() {
1767                     None
1768                 } else {
1769                     Some(l.clean(cx))
1770                 };
1771                 BorrowedRef {lifetime: lifetime, mutability: m.mutbl.clean(cx),
1772                              type_: box m.ty.clean(cx)}
1773             }
1774             TySlice(ref ty) => Slice(box ty.clean(cx)),
1775             TyArray(ref ty, length) => {
1776                 use rustc::middle::const_val::eval_length;
1777                 let n = eval_length(cx.tcx, length, "array length").unwrap();
1778                 Array(box ty.clean(cx), n)
1779             },
1780             TyTup(ref tys) => Tuple(tys.clean(cx)),
1781             TyPath(hir::QPath::Resolved(None, ref path)) => {
1782                 if let Some(new_ty) = cx.ty_substs.borrow().get(&path.def).cloned() {
1783                     return new_ty;
1784                 }
1785
1786                 let mut alias = None;
1787                 if let Def::TyAlias(def_id) = path.def {
1788                     // Substitute private type aliases
1789                     if let Some(node_id) = cx.tcx.hir.as_local_node_id(def_id) {
1790                         if !cx.access_levels.borrow().is_exported(def_id) {
1791                             alias = Some(&cx.tcx.hir.expect_item(node_id).node);
1792                         }
1793                     }
1794                 };
1795
1796                 if let Some(&hir::ItemTy(ref ty, ref generics)) = alias {
1797                     let provided_params = &path.segments.last().unwrap().parameters;
1798                     let mut ty_substs = FxHashMap();
1799                     let mut lt_substs = FxHashMap();
1800                     for (i, ty_param) in generics.ty_params.iter().enumerate() {
1801                         let ty_param_def = Def::TyParam(cx.tcx.hir.local_def_id(ty_param.id));
1802                         if let Some(ty) = provided_params.types.get(i).cloned() {
1803                             ty_substs.insert(ty_param_def, ty.unwrap().clean(cx));
1804                         } else if let Some(default) = ty_param.default.clone() {
1805                             ty_substs.insert(ty_param_def, default.unwrap().clean(cx));
1806                         }
1807                     }
1808                     for (i, lt_param) in generics.lifetimes.iter().enumerate() {
1809                         if let Some(lt) = provided_params.lifetimes.get(i).cloned() {
1810                             if !lt.is_elided() {
1811                                 lt_substs.insert(lt_param.lifetime.id, lt.clean(cx));
1812                             }
1813                         }
1814                     }
1815                     return cx.enter_alias(ty_substs, lt_substs, || ty.clean(cx));
1816                 }
1817                 resolve_type(cx, path.clean(cx), self.id)
1818             }
1819             TyPath(hir::QPath::Resolved(Some(ref qself), ref p)) => {
1820                 let mut segments: Vec<_> = p.segments.clone().into();
1821                 segments.pop();
1822                 let trait_path = hir::Path {
1823                     span: p.span,
1824                     def: Def::Trait(cx.tcx.associated_item(p.def.def_id()).container.id()),
1825                     segments: segments.into(),
1826                 };
1827                 Type::QPath {
1828                     name: p.segments.last().unwrap().name.clean(cx),
1829                     self_type: box qself.clean(cx),
1830                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
1831                 }
1832             }
1833             TyPath(hir::QPath::TypeRelative(ref qself, ref segment)) => {
1834                 let mut def = Def::Err;
1835                 let ty = hir_ty_to_ty(cx.tcx, self);
1836                 if let ty::TyProjection(proj) = ty.sty {
1837                     def = Def::Trait(proj.trait_ref(cx.tcx).def_id);
1838                 }
1839                 let trait_path = hir::Path {
1840                     span: self.span,
1841                     def,
1842                     segments: vec![].into(),
1843                 };
1844                 Type::QPath {
1845                     name: segment.name.clean(cx),
1846                     self_type: box qself.clean(cx),
1847                     trait_: box resolve_type(cx, trait_path.clean(cx), self.id)
1848                 }
1849             }
1850             TyTraitObject(ref bounds, ref lifetime) => {
1851                 match bounds[0].clean(cx).trait_ {
1852                     ResolvedPath { path, typarams: None, did, is_generic } => {
1853                         let mut bounds: Vec<_> = bounds[1..].iter().map(|bound| {
1854                             TraitBound(bound.clean(cx), hir::TraitBoundModifier::None)
1855                         }).collect();
1856                         if !lifetime.is_elided() {
1857                             bounds.push(RegionBound(lifetime.clean(cx)));
1858                         }
1859                         ResolvedPath {
1860                             path,
1861                             typarams: Some(bounds),
1862                             did,
1863                             is_generic,
1864                         }
1865                     }
1866                     _ => Infer // shouldn't happen
1867                 }
1868             }
1869             TyBareFn(ref barefn) => BareFunction(box barefn.clean(cx)),
1870             TyImplTrait(ref bounds) => ImplTrait(bounds.clean(cx)),
1871             TyInfer | TyErr => Infer,
1872             TyTypeof(..) => panic!("Unimplemented type {:?}", self.node),
1873         }
1874     }
1875 }
1876
1877 impl<'tcx> Clean<Type> for ty::Ty<'tcx> {
1878     fn clean(&self, cx: &DocContext) -> Type {
1879         match self.sty {
1880             ty::TyNever => Never,
1881             ty::TyBool => Primitive(PrimitiveType::Bool),
1882             ty::TyChar => Primitive(PrimitiveType::Char),
1883             ty::TyInt(int_ty) => Primitive(int_ty.into()),
1884             ty::TyUint(uint_ty) => Primitive(uint_ty.into()),
1885             ty::TyFloat(float_ty) => Primitive(float_ty.into()),
1886             ty::TyStr => Primitive(PrimitiveType::Str),
1887             ty::TySlice(ty) => Slice(box ty.clean(cx)),
1888             ty::TyArray(ty, n) => Array(box ty.clean(cx), n),
1889             ty::TyRawPtr(mt) => RawPointer(mt.mutbl.clean(cx), box mt.ty.clean(cx)),
1890             ty::TyRef(r, mt) => BorrowedRef {
1891                 lifetime: r.clean(cx),
1892                 mutability: mt.mutbl.clean(cx),
1893                 type_: box mt.ty.clean(cx),
1894             },
1895             ty::TyFnDef(..) |
1896             ty::TyFnPtr(_) => {
1897                 let ty = cx.tcx.lift(self).unwrap();
1898                 let sig = ty.fn_sig(cx.tcx);
1899                 BareFunction(box BareFunctionDecl {
1900                     unsafety: sig.unsafety(),
1901                     generics: Generics {
1902                         lifetimes: Vec::new(),
1903                         type_params: Vec::new(),
1904                         where_predicates: Vec::new()
1905                     },
1906                     decl: (cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID), sig).clean(cx),
1907                     abi: sig.abi(),
1908                 })
1909             }
1910             ty::TyAdt(def, substs) => {
1911                 let did = def.did;
1912                 let kind = match def.adt_kind() {
1913                     AdtKind::Struct => TypeKind::Struct,
1914                     AdtKind::Union => TypeKind::Union,
1915                     AdtKind::Enum => TypeKind::Enum,
1916                 };
1917                 inline::record_extern_fqn(cx, did, kind);
1918                 let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
1919                                          None, false, vec![], substs);
1920                 ResolvedPath {
1921                     path,
1922                     typarams: None,
1923                     did,
1924                     is_generic: false,
1925                 }
1926             }
1927             ty::TyDynamic(ref obj, ref reg) => {
1928                 if let Some(principal) = obj.principal() {
1929                     let did = principal.def_id();
1930                     inline::record_extern_fqn(cx, did, TypeKind::Trait);
1931
1932                     let mut typarams = vec![];
1933                     reg.clean(cx).map(|b| typarams.push(RegionBound(b)));
1934                     for did in obj.auto_traits() {
1935                         let empty = cx.tcx.intern_substs(&[]);
1936                         let path = external_path(cx, &cx.tcx.item_name(did).as_str(),
1937                             Some(did), false, vec![], empty);
1938                         inline::record_extern_fqn(cx, did, TypeKind::Trait);
1939                         let bound = TraitBound(PolyTrait {
1940                             trait_: ResolvedPath {
1941                                 path,
1942                                 typarams: None,
1943                                 did,
1944                                 is_generic: false,
1945                             },
1946                             lifetimes: vec![]
1947                         }, hir::TraitBoundModifier::None);
1948                         typarams.push(bound);
1949                     }
1950
1951                     let mut bindings = vec![];
1952                     for ty::Binder(ref pb) in obj.projection_bounds() {
1953                         bindings.push(TypeBinding {
1954                             name: cx.tcx.associated_item(pb.item_def_id).name.clean(cx),
1955                             ty: pb.ty.clean(cx)
1956                         });
1957                     }
1958
1959                     let path = external_path(cx, &cx.tcx.item_name(did).as_str(), Some(did),
1960                         false, bindings, principal.0.substs);
1961                     ResolvedPath {
1962                         path,
1963                         typarams: Some(typarams),
1964                         did,
1965                         is_generic: false,
1966                     }
1967                 } else {
1968                     Never
1969                 }
1970             }
1971             ty::TyTuple(ref t, _) => Tuple(t.clean(cx)),
1972
1973             ty::TyProjection(ref data) => data.clean(cx),
1974
1975             ty::TyParam(ref p) => Generic(p.name.to_string()),
1976
1977             ty::TyAnon(def_id, substs) => {
1978                 // Grab the "TraitA + TraitB" from `impl TraitA + TraitB`,
1979                 // by looking up the projections associated with the def_id.
1980                 let predicates_of = cx.tcx.predicates_of(def_id);
1981                 let substs = cx.tcx.lift(&substs).unwrap();
1982                 let bounds = predicates_of.instantiate(cx.tcx, substs);
1983                 ImplTrait(bounds.predicates.into_iter().filter_map(|predicate| {
1984                     predicate.to_opt_poly_trait_ref().clean(cx)
1985                 }).collect())
1986             }
1987
1988             ty::TyClosure(..) | ty::TyGenerator(..) => Tuple(vec![]), // FIXME(pcwalton)
1989
1990             ty::TyInfer(..) => panic!("TyInfer"),
1991             ty::TyError => panic!("TyError"),
1992         }
1993     }
1994 }
1995
1996 impl Clean<Item> for hir::StructField {
1997     fn clean(&self, cx: &DocContext) -> Item {
1998         Item {
1999             name: Some(self.name).clean(cx),
2000             attrs: self.attrs.clean(cx),
2001             source: self.span.clean(cx),
2002             visibility: self.vis.clean(cx),
2003             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2004             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2005             def_id: cx.tcx.hir.local_def_id(self.id),
2006             inner: StructFieldItem(self.ty.clean(cx)),
2007         }
2008     }
2009 }
2010
2011 impl<'tcx> Clean<Item> for ty::FieldDef {
2012     fn clean(&self, cx: &DocContext) -> Item {
2013         Item {
2014             name: Some(self.name).clean(cx),
2015             attrs: cx.tcx.get_attrs(self.did).clean(cx),
2016             source: cx.tcx.def_span(self.did).clean(cx),
2017             visibility: self.vis.clean(cx),
2018             stability: get_stability(cx, self.did),
2019             deprecation: get_deprecation(cx, self.did),
2020             def_id: self.did,
2021             inner: StructFieldItem(cx.tcx.type_of(self.did).clean(cx)),
2022         }
2023     }
2024 }
2025
2026 #[derive(Clone, PartialEq, Eq, RustcDecodable, RustcEncodable, Debug)]
2027 pub enum Visibility {
2028     Public,
2029     Inherited,
2030 }
2031
2032 impl Clean<Option<Visibility>> for hir::Visibility {
2033     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2034         Some(if *self == hir::Visibility::Public { Public } else { Inherited })
2035     }
2036 }
2037
2038 impl Clean<Option<Visibility>> for ty::Visibility {
2039     fn clean(&self, _: &DocContext) -> Option<Visibility> {
2040         Some(if *self == ty::Visibility::Public { Public } else { Inherited })
2041     }
2042 }
2043
2044 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2045 pub struct Struct {
2046     pub struct_type: doctree::StructType,
2047     pub generics: Generics,
2048     pub fields: Vec<Item>,
2049     pub fields_stripped: bool,
2050 }
2051
2052 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2053 pub struct Union {
2054     pub struct_type: doctree::StructType,
2055     pub generics: Generics,
2056     pub fields: Vec<Item>,
2057     pub fields_stripped: bool,
2058 }
2059
2060 impl Clean<Item> for doctree::Struct {
2061     fn clean(&self, cx: &DocContext) -> Item {
2062         Item {
2063             name: Some(self.name.clean(cx)),
2064             attrs: self.attrs.clean(cx),
2065             source: self.whence.clean(cx),
2066             def_id: cx.tcx.hir.local_def_id(self.id),
2067             visibility: self.vis.clean(cx),
2068             stability: self.stab.clean(cx),
2069             deprecation: self.depr.clean(cx),
2070             inner: StructItem(Struct {
2071                 struct_type: self.struct_type,
2072                 generics: self.generics.clean(cx),
2073                 fields: self.fields.clean(cx),
2074                 fields_stripped: false,
2075             }),
2076         }
2077     }
2078 }
2079
2080 impl Clean<Item> for doctree::Union {
2081     fn clean(&self, cx: &DocContext) -> Item {
2082         Item {
2083             name: Some(self.name.clean(cx)),
2084             attrs: self.attrs.clean(cx),
2085             source: self.whence.clean(cx),
2086             def_id: cx.tcx.hir.local_def_id(self.id),
2087             visibility: self.vis.clean(cx),
2088             stability: self.stab.clean(cx),
2089             deprecation: self.depr.clean(cx),
2090             inner: UnionItem(Union {
2091                 struct_type: self.struct_type,
2092                 generics: self.generics.clean(cx),
2093                 fields: self.fields.clean(cx),
2094                 fields_stripped: false,
2095             }),
2096         }
2097     }
2098 }
2099
2100 /// This is a more limited form of the standard Struct, different in that
2101 /// it lacks the things most items have (name, id, parameterization). Found
2102 /// only as a variant in an enum.
2103 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2104 pub struct VariantStruct {
2105     pub struct_type: doctree::StructType,
2106     pub fields: Vec<Item>,
2107     pub fields_stripped: bool,
2108 }
2109
2110 impl Clean<VariantStruct> for ::rustc::hir::VariantData {
2111     fn clean(&self, cx: &DocContext) -> VariantStruct {
2112         VariantStruct {
2113             struct_type: doctree::struct_type_from_def(self),
2114             fields: self.fields().iter().map(|x| x.clean(cx)).collect(),
2115             fields_stripped: false,
2116         }
2117     }
2118 }
2119
2120 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2121 pub struct Enum {
2122     pub variants: Vec<Item>,
2123     pub generics: Generics,
2124     pub variants_stripped: bool,
2125 }
2126
2127 impl Clean<Item> for doctree::Enum {
2128     fn clean(&self, cx: &DocContext) -> Item {
2129         Item {
2130             name: Some(self.name.clean(cx)),
2131             attrs: self.attrs.clean(cx),
2132             source: self.whence.clean(cx),
2133             def_id: cx.tcx.hir.local_def_id(self.id),
2134             visibility: self.vis.clean(cx),
2135             stability: self.stab.clean(cx),
2136             deprecation: self.depr.clean(cx),
2137             inner: EnumItem(Enum {
2138                 variants: self.variants.clean(cx),
2139                 generics: self.generics.clean(cx),
2140                 variants_stripped: false,
2141             }),
2142         }
2143     }
2144 }
2145
2146 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2147 pub struct Variant {
2148     pub kind: VariantKind,
2149 }
2150
2151 impl Clean<Item> for doctree::Variant {
2152     fn clean(&self, cx: &DocContext) -> Item {
2153         Item {
2154             name: Some(self.name.clean(cx)),
2155             attrs: self.attrs.clean(cx),
2156             source: self.whence.clean(cx),
2157             visibility: None,
2158             stability: self.stab.clean(cx),
2159             deprecation: self.depr.clean(cx),
2160             def_id: cx.tcx.hir.local_def_id(self.def.id()),
2161             inner: VariantItem(Variant {
2162                 kind: self.def.clean(cx),
2163             }),
2164         }
2165     }
2166 }
2167
2168 impl<'tcx> Clean<Item> for ty::VariantDef {
2169     fn clean(&self, cx: &DocContext) -> Item {
2170         let kind = match self.ctor_kind {
2171             CtorKind::Const => VariantKind::CLike,
2172             CtorKind::Fn => {
2173                 VariantKind::Tuple(
2174                     self.fields.iter().map(|f| cx.tcx.type_of(f.did).clean(cx)).collect()
2175                 )
2176             }
2177             CtorKind::Fictive => {
2178                 VariantKind::Struct(VariantStruct {
2179                     struct_type: doctree::Plain,
2180                     fields_stripped: false,
2181                     fields: self.fields.iter().map(|field| {
2182                         Item {
2183                             source: cx.tcx.def_span(field.did).clean(cx),
2184                             name: Some(field.name.clean(cx)),
2185                             attrs: cx.tcx.get_attrs(field.did).clean(cx),
2186                             visibility: field.vis.clean(cx),
2187                             def_id: field.did,
2188                             stability: get_stability(cx, field.did),
2189                             deprecation: get_deprecation(cx, field.did),
2190                             inner: StructFieldItem(cx.tcx.type_of(field.did).clean(cx))
2191                         }
2192                     }).collect()
2193                 })
2194             }
2195         };
2196         Item {
2197             name: Some(self.name.clean(cx)),
2198             attrs: inline::load_attrs(cx, self.did),
2199             source: cx.tcx.def_span(self.did).clean(cx),
2200             visibility: Some(Inherited),
2201             def_id: self.did,
2202             inner: VariantItem(Variant { kind: kind }),
2203             stability: get_stability(cx, self.did),
2204             deprecation: get_deprecation(cx, self.did),
2205         }
2206     }
2207 }
2208
2209 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2210 pub enum VariantKind {
2211     CLike,
2212     Tuple(Vec<Type>),
2213     Struct(VariantStruct),
2214 }
2215
2216 impl Clean<VariantKind> for hir::VariantData {
2217     fn clean(&self, cx: &DocContext) -> VariantKind {
2218         if self.is_struct() {
2219             VariantKind::Struct(self.clean(cx))
2220         } else if self.is_unit() {
2221             VariantKind::CLike
2222         } else {
2223             VariantKind::Tuple(self.fields().iter().map(|x| x.ty.clean(cx)).collect())
2224         }
2225     }
2226 }
2227
2228 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2229 pub struct Span {
2230     pub filename: String,
2231     pub loline: usize,
2232     pub locol: usize,
2233     pub hiline: usize,
2234     pub hicol: usize,
2235 }
2236
2237 impl Span {
2238     fn empty() -> Span {
2239         Span {
2240             filename: "".to_string(),
2241             loline: 0, locol: 0,
2242             hiline: 0, hicol: 0,
2243         }
2244     }
2245 }
2246
2247 impl Clean<Span> for syntax_pos::Span {
2248     fn clean(&self, cx: &DocContext) -> Span {
2249         if *self == DUMMY_SP {
2250             return Span::empty();
2251         }
2252
2253         let cm = cx.sess().codemap();
2254         let filename = cm.span_to_filename(*self);
2255         let lo = cm.lookup_char_pos(self.lo());
2256         let hi = cm.lookup_char_pos(self.hi());
2257         Span {
2258             filename: filename.to_string(),
2259             loline: lo.line,
2260             locol: lo.col.to_usize(),
2261             hiline: hi.line,
2262             hicol: hi.col.to_usize(),
2263         }
2264     }
2265 }
2266
2267 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2268 pub struct Path {
2269     pub global: bool,
2270     pub def: Def,
2271     pub segments: Vec<PathSegment>,
2272 }
2273
2274 impl Path {
2275     pub fn singleton(name: String) -> Path {
2276         Path {
2277             global: false,
2278             def: Def::Err,
2279             segments: vec![PathSegment {
2280                 name,
2281                 params: PathParameters::AngleBracketed {
2282                     lifetimes: Vec::new(),
2283                     types: Vec::new(),
2284                     bindings: Vec::new()
2285                 }
2286             }]
2287         }
2288     }
2289
2290     pub fn last_name(&self) -> &str {
2291         self.segments.last().unwrap().name.as_str()
2292     }
2293 }
2294
2295 impl Clean<Path> for hir::Path {
2296     fn clean(&self, cx: &DocContext) -> Path {
2297         Path {
2298             global: self.is_global(),
2299             def: self.def,
2300             segments: if self.is_global() { &self.segments[1..] } else { &self.segments }.clean(cx),
2301         }
2302     }
2303 }
2304
2305 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2306 pub enum PathParameters {
2307     AngleBracketed {
2308         lifetimes: Vec<Lifetime>,
2309         types: Vec<Type>,
2310         bindings: Vec<TypeBinding>,
2311     },
2312     Parenthesized {
2313         inputs: Vec<Type>,
2314         output: Option<Type>,
2315     }
2316 }
2317
2318 impl Clean<PathParameters> for hir::PathParameters {
2319     fn clean(&self, cx: &DocContext) -> PathParameters {
2320         if self.parenthesized {
2321             let output = self.bindings[0].ty.clean(cx);
2322             PathParameters::Parenthesized {
2323                 inputs: self.inputs().clean(cx),
2324                 output: if output != Type::Tuple(Vec::new()) { Some(output) } else { None }
2325             }
2326         } else {
2327             PathParameters::AngleBracketed {
2328                 lifetimes: if self.lifetimes.iter().all(|lt| lt.is_elided()) {
2329                     vec![]
2330                 } else {
2331                     self.lifetimes.clean(cx)
2332                 },
2333                 types: self.types.clean(cx),
2334                 bindings: self.bindings.clean(cx),
2335             }
2336         }
2337     }
2338 }
2339
2340 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2341 pub struct PathSegment {
2342     pub name: String,
2343     pub params: PathParameters,
2344 }
2345
2346 impl Clean<PathSegment> for hir::PathSegment {
2347     fn clean(&self, cx: &DocContext) -> PathSegment {
2348         PathSegment {
2349             name: self.name.clean(cx),
2350             params: self.parameters.clean(cx)
2351         }
2352     }
2353 }
2354
2355 fn qpath_to_string(p: &hir::QPath) -> String {
2356     let segments = match *p {
2357         hir::QPath::Resolved(_, ref path) => &path.segments,
2358         hir::QPath::TypeRelative(_, ref segment) => return segment.name.to_string(),
2359     };
2360
2361     let mut s = String::new();
2362     for (i, seg) in segments.iter().enumerate() {
2363         if i > 0 {
2364             s.push_str("::");
2365         }
2366         if seg.name != keywords::CrateRoot.name() {
2367             s.push_str(&*seg.name.as_str());
2368         }
2369     }
2370     s
2371 }
2372
2373 impl Clean<String> for ast::Name {
2374     fn clean(&self, _: &DocContext) -> String {
2375         self.to_string()
2376     }
2377 }
2378
2379 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2380 pub struct Typedef {
2381     pub type_: Type,
2382     pub generics: Generics,
2383 }
2384
2385 impl Clean<Item> for doctree::Typedef {
2386     fn clean(&self, cx: &DocContext) -> Item {
2387         Item {
2388             name: Some(self.name.clean(cx)),
2389             attrs: self.attrs.clean(cx),
2390             source: self.whence.clean(cx),
2391             def_id: cx.tcx.hir.local_def_id(self.id.clone()),
2392             visibility: self.vis.clean(cx),
2393             stability: self.stab.clean(cx),
2394             deprecation: self.depr.clean(cx),
2395             inner: TypedefItem(Typedef {
2396                 type_: self.ty.clean(cx),
2397                 generics: self.gen.clean(cx),
2398             }, false),
2399         }
2400     }
2401 }
2402
2403 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
2404 pub struct BareFunctionDecl {
2405     pub unsafety: hir::Unsafety,
2406     pub generics: Generics,
2407     pub decl: FnDecl,
2408     pub abi: Abi,
2409 }
2410
2411 impl Clean<BareFunctionDecl> for hir::BareFnTy {
2412     fn clean(&self, cx: &DocContext) -> BareFunctionDecl {
2413         BareFunctionDecl {
2414             unsafety: self.unsafety,
2415             generics: Generics {
2416                 lifetimes: self.lifetimes.clean(cx),
2417                 type_params: Vec::new(),
2418                 where_predicates: Vec::new()
2419             },
2420             decl: (&*self.decl, &[][..]).clean(cx),
2421             abi: self.abi,
2422         }
2423     }
2424 }
2425
2426 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2427 pub struct Static {
2428     pub type_: Type,
2429     pub mutability: Mutability,
2430     /// It's useful to have the value of a static documented, but I have no
2431     /// desire to represent expressions (that'd basically be all of the AST,
2432     /// which is huge!). So, have a string.
2433     pub expr: String,
2434 }
2435
2436 impl Clean<Item> for doctree::Static {
2437     fn clean(&self, cx: &DocContext) -> Item {
2438         debug!("cleaning static {}: {:?}", self.name.clean(cx), self);
2439         Item {
2440             name: Some(self.name.clean(cx)),
2441             attrs: self.attrs.clean(cx),
2442             source: self.whence.clean(cx),
2443             def_id: cx.tcx.hir.local_def_id(self.id),
2444             visibility: self.vis.clean(cx),
2445             stability: self.stab.clean(cx),
2446             deprecation: self.depr.clean(cx),
2447             inner: StaticItem(Static {
2448                 type_: self.type_.clean(cx),
2449                 mutability: self.mutability.clean(cx),
2450                 expr: print_const_expr(cx, self.expr),
2451             }),
2452         }
2453     }
2454 }
2455
2456 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2457 pub struct Constant {
2458     pub type_: Type,
2459     pub expr: String,
2460 }
2461
2462 impl Clean<Item> for doctree::Constant {
2463     fn clean(&self, cx: &DocContext) -> Item {
2464         Item {
2465             name: Some(self.name.clean(cx)),
2466             attrs: self.attrs.clean(cx),
2467             source: self.whence.clean(cx),
2468             def_id: cx.tcx.hir.local_def_id(self.id),
2469             visibility: self.vis.clean(cx),
2470             stability: self.stab.clean(cx),
2471             deprecation: self.depr.clean(cx),
2472             inner: ConstantItem(Constant {
2473                 type_: self.type_.clean(cx),
2474                 expr: print_const_expr(cx, self.expr),
2475             }),
2476         }
2477     }
2478 }
2479
2480 #[derive(Debug, Clone, RustcEncodable, RustcDecodable, PartialEq, Copy)]
2481 pub enum Mutability {
2482     Mutable,
2483     Immutable,
2484 }
2485
2486 impl Clean<Mutability> for hir::Mutability {
2487     fn clean(&self, _: &DocContext) -> Mutability {
2488         match self {
2489             &hir::MutMutable => Mutable,
2490             &hir::MutImmutable => Immutable,
2491         }
2492     }
2493 }
2494
2495 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Copy, Debug)]
2496 pub enum ImplPolarity {
2497     Positive,
2498     Negative,
2499 }
2500
2501 impl Clean<ImplPolarity> for hir::ImplPolarity {
2502     fn clean(&self, _: &DocContext) -> ImplPolarity {
2503         match self {
2504             &hir::ImplPolarity::Positive => ImplPolarity::Positive,
2505             &hir::ImplPolarity::Negative => ImplPolarity::Negative,
2506         }
2507     }
2508 }
2509
2510 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2511 pub struct Impl {
2512     pub unsafety: hir::Unsafety,
2513     pub generics: Generics,
2514     pub provided_trait_methods: FxHashSet<String>,
2515     pub trait_: Option<Type>,
2516     pub for_: Type,
2517     pub items: Vec<Item>,
2518     pub polarity: Option<ImplPolarity>,
2519 }
2520
2521 impl Clean<Vec<Item>> for doctree::Impl {
2522     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2523         let mut ret = Vec::new();
2524         let trait_ = self.trait_.clean(cx);
2525         let items = self.items.clean(cx);
2526
2527         // If this impl block is an implementation of the Deref trait, then we
2528         // need to try inlining the target's inherent impl blocks as well.
2529         if trait_.def_id() == cx.tcx.lang_items.deref_trait() {
2530             build_deref_target_impls(cx, &items, &mut ret);
2531         }
2532
2533         let provided = trait_.def_id().map(|did| {
2534             cx.tcx.provided_trait_methods(did)
2535                   .into_iter()
2536                   .map(|meth| meth.name.to_string())
2537                   .collect()
2538         }).unwrap_or(FxHashSet());
2539
2540         ret.push(Item {
2541             name: None,
2542             attrs: self.attrs.clean(cx),
2543             source: self.whence.clean(cx),
2544             def_id: cx.tcx.hir.local_def_id(self.id),
2545             visibility: self.vis.clean(cx),
2546             stability: self.stab.clean(cx),
2547             deprecation: self.depr.clean(cx),
2548             inner: ImplItem(Impl {
2549                 unsafety: self.unsafety,
2550                 generics: self.generics.clean(cx),
2551                 provided_trait_methods: provided,
2552                 trait_,
2553                 for_: self.for_.clean(cx),
2554                 items,
2555                 polarity: Some(self.polarity.clean(cx)),
2556             }),
2557         });
2558         ret
2559     }
2560 }
2561
2562 fn build_deref_target_impls(cx: &DocContext,
2563                             items: &[Item],
2564                             ret: &mut Vec<Item>) {
2565     use self::PrimitiveType::*;
2566     let tcx = cx.tcx;
2567
2568     for item in items {
2569         let target = match item.inner {
2570             TypedefItem(ref t, true) => &t.type_,
2571             _ => continue,
2572         };
2573         let primitive = match *target {
2574             ResolvedPath { did, .. } if did.is_local() => continue,
2575             ResolvedPath { did, .. } => {
2576                 ret.extend(inline::build_impls(cx, did));
2577                 continue
2578             }
2579             _ => match target.primitive_type() {
2580                 Some(prim) => prim,
2581                 None => continue,
2582             }
2583         };
2584         let did = match primitive {
2585             Isize => tcx.lang_items.isize_impl(),
2586             I8 => tcx.lang_items.i8_impl(),
2587             I16 => tcx.lang_items.i16_impl(),
2588             I32 => tcx.lang_items.i32_impl(),
2589             I64 => tcx.lang_items.i64_impl(),
2590             I128 => tcx.lang_items.i128_impl(),
2591             Usize => tcx.lang_items.usize_impl(),
2592             U8 => tcx.lang_items.u8_impl(),
2593             U16 => tcx.lang_items.u16_impl(),
2594             U32 => tcx.lang_items.u32_impl(),
2595             U64 => tcx.lang_items.u64_impl(),
2596             U128 => tcx.lang_items.u128_impl(),
2597             F32 => tcx.lang_items.f32_impl(),
2598             F64 => tcx.lang_items.f64_impl(),
2599             Char => tcx.lang_items.char_impl(),
2600             Bool => None,
2601             Str => tcx.lang_items.str_impl(),
2602             Slice => tcx.lang_items.slice_impl(),
2603             Array => tcx.lang_items.slice_impl(),
2604             Tuple => None,
2605             RawPointer => tcx.lang_items.const_ptr_impl(),
2606             Reference => None,
2607             Fn => None,
2608         };
2609         if let Some(did) = did {
2610             if !did.is_local() {
2611                 inline::build_impl(cx, did, ret);
2612             }
2613         }
2614     }
2615 }
2616
2617 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2618 pub struct DefaultImpl {
2619     pub unsafety: hir::Unsafety,
2620     pub trait_: Type,
2621 }
2622
2623 impl Clean<Item> for doctree::DefaultImpl {
2624     fn clean(&self, cx: &DocContext) -> Item {
2625         Item {
2626             name: None,
2627             attrs: self.attrs.clean(cx),
2628             source: self.whence.clean(cx),
2629             def_id: cx.tcx.hir.local_def_id(self.id),
2630             visibility: Some(Public),
2631             stability: None,
2632             deprecation: None,
2633             inner: DefaultImplItem(DefaultImpl {
2634                 unsafety: self.unsafety,
2635                 trait_: self.trait_.clean(cx),
2636             }),
2637         }
2638     }
2639 }
2640
2641 impl Clean<Item> for doctree::ExternCrate {
2642     fn clean(&self, cx: &DocContext) -> Item {
2643         Item {
2644             name: None,
2645             attrs: self.attrs.clean(cx),
2646             source: self.whence.clean(cx),
2647             def_id: DefId { krate: self.cnum, index: CRATE_DEF_INDEX },
2648             visibility: self.vis.clean(cx),
2649             stability: None,
2650             deprecation: None,
2651             inner: ExternCrateItem(self.name.clean(cx), self.path.clone())
2652         }
2653     }
2654 }
2655
2656 impl Clean<Vec<Item>> for doctree::Import {
2657     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2658         // We consider inlining the documentation of `pub use` statements, but we
2659         // forcefully don't inline if this is not public or if the
2660         // #[doc(no_inline)] attribute is present.
2661         // Don't inline doc(hidden) imports so they can be stripped at a later stage.
2662         let denied = self.vis != hir::Public || self.attrs.iter().any(|a| {
2663             a.name().unwrap() == "doc" && match a.meta_item_list() {
2664                 Some(l) => attr::list_contains_name(&l, "no_inline") ||
2665                            attr::list_contains_name(&l, "hidden"),
2666                 None => false,
2667             }
2668         });
2669         let path = self.path.clean(cx);
2670         let inner = if self.glob {
2671             Import::Glob(resolve_use_source(cx, path))
2672         } else {
2673             let name = self.name;
2674             if !denied {
2675                 if let Some(items) = inline::try_inline(cx, path.def, name) {
2676                     return items;
2677                 }
2678             }
2679             Import::Simple(name.clean(cx), resolve_use_source(cx, path))
2680         };
2681         vec![Item {
2682             name: None,
2683             attrs: self.attrs.clean(cx),
2684             source: self.whence.clean(cx),
2685             def_id: cx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
2686             visibility: self.vis.clean(cx),
2687             stability: None,
2688             deprecation: None,
2689             inner: ImportItem(inner)
2690         }]
2691     }
2692 }
2693
2694 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2695 pub enum Import {
2696     // use source as str;
2697     Simple(String, ImportSource),
2698     // use source::*;
2699     Glob(ImportSource)
2700 }
2701
2702 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2703 pub struct ImportSource {
2704     pub path: Path,
2705     pub did: Option<DefId>,
2706 }
2707
2708 impl Clean<Vec<Item>> for hir::ForeignMod {
2709     fn clean(&self, cx: &DocContext) -> Vec<Item> {
2710         let mut items = self.items.clean(cx);
2711         for item in &mut items {
2712             if let ForeignFunctionItem(ref mut f) = item.inner {
2713                 f.abi = self.abi;
2714             }
2715         }
2716         items
2717     }
2718 }
2719
2720 impl Clean<Item> for hir::ForeignItem {
2721     fn clean(&self, cx: &DocContext) -> Item {
2722         let inner = match self.node {
2723             hir::ForeignItemFn(ref decl, ref names, ref generics) => {
2724                 ForeignFunctionItem(Function {
2725                     decl: (&**decl, &names[..]).clean(cx),
2726                     generics: generics.clean(cx),
2727                     unsafety: hir::Unsafety::Unsafe,
2728                     abi: Abi::Rust,
2729                     constness: hir::Constness::NotConst,
2730                 })
2731             }
2732             hir::ForeignItemStatic(ref ty, mutbl) => {
2733                 ForeignStaticItem(Static {
2734                     type_: ty.clean(cx),
2735                     mutability: if mutbl {Mutable} else {Immutable},
2736                     expr: "".to_string(),
2737                 })
2738             }
2739         };
2740         Item {
2741             name: Some(self.name.clean(cx)),
2742             attrs: self.attrs.clean(cx),
2743             source: self.span.clean(cx),
2744             def_id: cx.tcx.hir.local_def_id(self.id),
2745             visibility: self.vis.clean(cx),
2746             stability: get_stability(cx, cx.tcx.hir.local_def_id(self.id)),
2747             deprecation: get_deprecation(cx, cx.tcx.hir.local_def_id(self.id)),
2748             inner,
2749         }
2750     }
2751 }
2752
2753 // Utilities
2754
2755 trait ToSource {
2756     fn to_src(&self, cx: &DocContext) -> String;
2757 }
2758
2759 impl ToSource for syntax_pos::Span {
2760     fn to_src(&self, cx: &DocContext) -> String {
2761         debug!("converting span {:?} to snippet", self.clean(cx));
2762         let sn = match cx.sess().codemap().span_to_snippet(*self) {
2763             Ok(x) => x.to_string(),
2764             Err(_) => "".to_string()
2765         };
2766         debug!("got snippet {}", sn);
2767         sn
2768     }
2769 }
2770
2771 fn name_from_pat(p: &hir::Pat) -> String {
2772     use rustc::hir::*;
2773     debug!("Trying to get a name from pattern: {:?}", p);
2774
2775     match p.node {
2776         PatKind::Wild => "_".to_string(),
2777         PatKind::Binding(_, _, ref p, _) => p.node.to_string(),
2778         PatKind::TupleStruct(ref p, ..) | PatKind::Path(ref p) => qpath_to_string(p),
2779         PatKind::Struct(ref name, ref fields, etc) => {
2780             format!("{} {{ {}{} }}", qpath_to_string(name),
2781                 fields.iter().map(|&Spanned { node: ref fp, .. }|
2782                                   format!("{}: {}", fp.name, name_from_pat(&*fp.pat)))
2783                              .collect::<Vec<String>>().join(", "),
2784                 if etc { ", ..." } else { "" }
2785             )
2786         }
2787         PatKind::Tuple(ref elts, _) => format!("({})", elts.iter().map(|p| name_from_pat(&**p))
2788                                             .collect::<Vec<String>>().join(", ")),
2789         PatKind::Box(ref p) => name_from_pat(&**p),
2790         PatKind::Ref(ref p, _) => name_from_pat(&**p),
2791         PatKind::Lit(..) => {
2792             warn!("tried to get argument name from PatKind::Lit, \
2793                   which is silly in function arguments");
2794             "()".to_string()
2795         },
2796         PatKind::Range(..) => panic!("tried to get argument name from PatKind::Range, \
2797                               which is not allowed in function arguments"),
2798         PatKind::Slice(ref begin, ref mid, ref end) => {
2799             let begin = begin.iter().map(|p| name_from_pat(&**p));
2800             let mid = mid.as_ref().map(|p| format!("..{}", name_from_pat(&**p))).into_iter();
2801             let end = end.iter().map(|p| name_from_pat(&**p));
2802             format!("[{}]", begin.chain(mid).chain(end).collect::<Vec<_>>().join(", "))
2803         },
2804     }
2805 }
2806
2807 fn print_const_expr(cx: &DocContext, body: hir::BodyId) -> String {
2808     cx.tcx.hir.node_to_pretty_string(body.node_id)
2809 }
2810
2811 /// Given a type Path, resolve it to a Type using the TyCtxt
2812 fn resolve_type(cx: &DocContext,
2813                 path: Path,
2814                 id: ast::NodeId) -> Type {
2815     debug!("resolve_type({:?},{:?})", path, id);
2816
2817     let is_generic = match path.def {
2818         Def::PrimTy(p) => match p {
2819             hir::TyStr => return Primitive(PrimitiveType::Str),
2820             hir::TyBool => return Primitive(PrimitiveType::Bool),
2821             hir::TyChar => return Primitive(PrimitiveType::Char),
2822             hir::TyInt(int_ty) => return Primitive(int_ty.into()),
2823             hir::TyUint(uint_ty) => return Primitive(uint_ty.into()),
2824             hir::TyFloat(float_ty) => return Primitive(float_ty.into()),
2825         },
2826         Def::SelfTy(..) if path.segments.len() == 1 => {
2827             return Generic(keywords::SelfType.name().to_string());
2828         }
2829         Def::TyParam(..) if path.segments.len() == 1 => {
2830             return Generic(format!("{:#}", path));
2831         }
2832         Def::SelfTy(..) | Def::TyParam(..) | Def::AssociatedTy(..) => true,
2833         _ => false,
2834     };
2835     let did = register_def(&*cx, path.def);
2836     ResolvedPath { path: path, typarams: None, did: did, is_generic: is_generic }
2837 }
2838
2839 fn register_def(cx: &DocContext, def: Def) -> DefId {
2840     debug!("register_def({:?})", def);
2841
2842     let (did, kind) = match def {
2843         Def::Fn(i) => (i, TypeKind::Function),
2844         Def::TyAlias(i) => (i, TypeKind::Typedef),
2845         Def::Enum(i) => (i, TypeKind::Enum),
2846         Def::Trait(i) => (i, TypeKind::Trait),
2847         Def::Struct(i) => (i, TypeKind::Struct),
2848         Def::Union(i) => (i, TypeKind::Union),
2849         Def::Mod(i) => (i, TypeKind::Module),
2850         Def::Static(i, _) => (i, TypeKind::Static),
2851         Def::Variant(i) => (cx.tcx.parent_def_id(i).unwrap(), TypeKind::Enum),
2852         Def::SelfTy(Some(def_id), _) => (def_id, TypeKind::Trait),
2853         Def::SelfTy(_, Some(impl_def_id)) => {
2854             return impl_def_id
2855         }
2856         _ => return def.def_id()
2857     };
2858     if did.is_local() { return did }
2859     inline::record_extern_fqn(cx, did, kind);
2860     if let TypeKind::Trait = kind {
2861         let t = inline::build_external_trait(cx, did);
2862         cx.external_traits.borrow_mut().insert(did, t);
2863     }
2864     did
2865 }
2866
2867 fn resolve_use_source(cx: &DocContext, path: Path) -> ImportSource {
2868     ImportSource {
2869         did: if path.def == Def::Err {
2870             None
2871         } else {
2872             Some(register_def(cx, path.def))
2873         },
2874         path,
2875     }
2876 }
2877
2878 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2879 pub struct Macro {
2880     pub source: String,
2881     pub imported_from: Option<String>,
2882 }
2883
2884 impl Clean<Item> for doctree::Macro {
2885     fn clean(&self, cx: &DocContext) -> Item {
2886         let name = self.name.clean(cx);
2887         Item {
2888             name: Some(name.clone()),
2889             attrs: self.attrs.clean(cx),
2890             source: self.whence.clean(cx),
2891             visibility: Some(Public),
2892             stability: self.stab.clean(cx),
2893             deprecation: self.depr.clean(cx),
2894             def_id: self.def_id,
2895             inner: MacroItem(Macro {
2896                 source: format!("macro_rules! {} {{\n{}}}",
2897                                 name,
2898                                 self.matchers.iter().map(|span| {
2899                                     format!("    {} => {{ ... }};\n", span.to_src(cx))
2900                                 }).collect::<String>()),
2901                 imported_from: self.imported_from.clean(cx),
2902             }),
2903         }
2904     }
2905 }
2906
2907 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2908 pub struct Stability {
2909     pub level: stability::StabilityLevel,
2910     pub feature: String,
2911     pub since: String,
2912     pub deprecated_since: String,
2913     pub deprecated_reason: String,
2914     pub unstable_reason: String,
2915     pub issue: Option<u32>
2916 }
2917
2918 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
2919 pub struct Deprecation {
2920     pub since: String,
2921     pub note: String,
2922 }
2923
2924 impl Clean<Stability> for attr::Stability {
2925     fn clean(&self, _: &DocContext) -> Stability {
2926         Stability {
2927             level: stability::StabilityLevel::from_attr_level(&self.level),
2928             feature: self.feature.to_string(),
2929             since: match self.level {
2930                 attr::Stable {ref since} => since.to_string(),
2931                 _ => "".to_string(),
2932             },
2933             deprecated_since: match self.rustc_depr {
2934                 Some(attr::RustcDeprecation {ref since, ..}) => since.to_string(),
2935                 _=> "".to_string(),
2936             },
2937             deprecated_reason: match self.rustc_depr {
2938                 Some(ref depr) => depr.reason.to_string(),
2939                 _ => "".to_string(),
2940             },
2941             unstable_reason: match self.level {
2942                 attr::Unstable { reason: Some(ref reason), .. } => reason.to_string(),
2943                 _ => "".to_string(),
2944             },
2945             issue: match self.level {
2946                 attr::Unstable {issue, ..} => Some(issue),
2947                 _ => None,
2948             }
2949         }
2950     }
2951 }
2952
2953 impl<'a> Clean<Stability> for &'a attr::Stability {
2954     fn clean(&self, dc: &DocContext) -> Stability {
2955         (**self).clean(dc)
2956     }
2957 }
2958
2959 impl Clean<Deprecation> for attr::Deprecation {
2960     fn clean(&self, _: &DocContext) -> Deprecation {
2961         Deprecation {
2962             since: self.since.as_ref().map_or("".to_string(), |s| s.to_string()),
2963             note: self.note.as_ref().map_or("".to_string(), |s| s.to_string()),
2964         }
2965     }
2966 }
2967
2968 /// An equality constraint on an associated type, e.g. `A=Bar` in `Foo<A=Bar>`
2969 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable, Debug)]
2970 pub struct TypeBinding {
2971     pub name: String,
2972     pub ty: Type
2973 }
2974
2975 impl Clean<TypeBinding> for hir::TypeBinding {
2976     fn clean(&self, cx: &DocContext) -> TypeBinding {
2977         TypeBinding {
2978             name: self.name.clean(cx),
2979             ty: self.ty.clean(cx)
2980         }
2981     }
2982 }