src/librustc_metadata/encoder.rs

   1 // Copyright 2012-2015 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 use cstore;
  12 use index::Index;
  13 use schema::*;
  14
  15 use rustc::middle::cstore::{InlinedItemRef, LinkMeta};
  16 use rustc::middle::cstore::{LinkagePreference, NativeLibrary};
  17 use rustc::hir::def;
  18 use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefIndex, DefId};
  19 use rustc::middle::dependency_format::Linkage;
  20 use rustc::middle::lang_items;
  21 use rustc::mir;
  22 use rustc::traits::specialization_graph;
  23 use rustc::ty::{self, Ty, TyCtxt};
  24
  25 use rustc::session::config::{self, CrateTypeProcMacro};
  26 use rustc::util::nodemap::{FxHashMap, NodeSet};
  27
  28 use rustc_serialize::{Encodable, Encoder, SpecializedEncoder, opaque};
  29 use std::hash::Hash;
  30 use std::intrinsics;
  31 use std::io::prelude::*;
  32 use std::io::Cursor;
  33 use std::rc::Rc;
  34 use std::u32;
  35 use syntax::ast::{self, CRATE_NODE_ID};
  36 use syntax::attr;
  37 use syntax::symbol::Symbol;
  38 use syntax_pos;
  39
  40 use rustc::hir::{self, PatKind};
  41 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  42 use rustc::hir::intravisit::Visitor;
  43 use rustc::hir::intravisit;
  44
  45 use super::index_builder::{FromId, IndexBuilder, Untracked};
  46
  47 pub struct EncodeContext<'a, 'tcx: 'a> {
  48     opaque: opaque::Encoder<'a>,
  49     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
  50     reexports: &'a def::ExportMap,
  51     link_meta: &'a LinkMeta,
  52     cstore: &'a cstore::CStore,
  53     reachable: &'a NodeSet,
  54
  55     lazy_state: LazyState,
  56     type_shorthands: FxHashMap<Ty<'tcx>, usize>,
  57     predicate_shorthands: FxHashMap<ty::Predicate<'tcx>, usize>,
  58 }
  59
  60 macro_rules! encoder_methods {
  61     ($($name:ident($ty:ty);)*) => {
  62         $(fn $name(&mut self, value: $ty) -> Result<(), Self::Error> {
  63             self.opaque.$name(value)
  64         })*
  65     }
  66 }
  67
  68 impl<'a, 'tcx> Encoder for EncodeContext<'a, 'tcx> {
  69     type Error = <opaque::Encoder<'a> as Encoder>::Error;
  70
  71     fn emit_nil(&mut self) -> Result<(), Self::Error> {
  72         Ok(())
  73     }
  74
  75     encoder_methods! {
  76         emit_usize(usize);
  77         emit_u64(u64);
  78         emit_u32(u32);
  79         emit_u16(u16);
  80         emit_u8(u8);
  81
  82         emit_isize(isize);
  83         emit_i64(i64);
  84         emit_i32(i32);
  85         emit_i16(i16);
  86         emit_i8(i8);
  87
  88         emit_bool(bool);
  89         emit_f64(f64);
  90         emit_f32(f32);
  91         emit_char(char);
  92         emit_str(&str);
  93     }
  94 }
  95
  96 impl<'a, 'tcx, T> SpecializedEncoder<Lazy<T>> for EncodeContext<'a, 'tcx> {
  97     fn specialized_encode(&mut self, lazy: &Lazy<T>) -> Result<(), Self::Error> {
  98         self.emit_lazy_distance(lazy.position, Lazy::<T>::min_size())
  99     }
 100 }
 101
 102 impl<'a, 'tcx, T> SpecializedEncoder<LazySeq<T>> for EncodeContext<'a, 'tcx> {
 103     fn specialized_encode(&mut self, seq: &LazySeq<T>) -> Result<(), Self::Error> {
 104         self.emit_usize(seq.len)?;
 105         if seq.len == 0 {
 106             return Ok(());
 107         }
 108         self.emit_lazy_distance(seq.position, LazySeq::<T>::min_size(seq.len))
 109     }
 110 }
 111
 112 impl<'a, 'tcx> SpecializedEncoder<Ty<'tcx>> for EncodeContext<'a, 'tcx> {
 113     fn specialized_encode(&mut self, ty: &Ty<'tcx>) -> Result<(), Self::Error> {
 114         self.encode_with_shorthand(ty, &ty.sty, |ecx| &mut ecx.type_shorthands)
 115     }
 116 }
 117
 118 impl<'a, 'tcx> SpecializedEncoder<ty::GenericPredicates<'tcx>> for EncodeContext<'a, 'tcx> {
 119     fn specialized_encode(&mut self,
 120                           predicates: &ty::GenericPredicates<'tcx>)
 121                           -> Result<(), Self::Error> {
 122         predicates.parent.encode(self)?;
 123         predicates.predicates.len().encode(self)?;
 124         for predicate in &predicates.predicates {
 125             self.encode_with_shorthand(predicate, predicate, |ecx| &mut ecx.predicate_shorthands)?
 126         }
 127         Ok(())
 128     }
 129 }
 130
 131 impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 132     pub fn position(&self) -> usize {
 133         self.opaque.position()
 134     }
 135
 136     fn emit_node<F: FnOnce(&mut Self, usize) -> R, R>(&mut self, f: F) -> R {
 137         assert_eq!(self.lazy_state, LazyState::NoNode);
 138         let pos = self.position();
 139         self.lazy_state = LazyState::NodeStart(pos);
 140         let r = f(self, pos);
 141         self.lazy_state = LazyState::NoNode;
 142         r
 143     }
 144
 145     fn emit_lazy_distance(&mut self,
 146                           position: usize,
 147                           min_size: usize)
 148                           -> Result<(), <Self as Encoder>::Error> {
 149         let min_end = position + min_size;
 150         let distance = match self.lazy_state {
 151             LazyState::NoNode => bug!("emit_lazy_distance: outside of a metadata node"),
 152             LazyState::NodeStart(start) => {
 153                 assert!(min_end <= start);
 154                 start - min_end
 155             }
 156             LazyState::Previous(last_min_end) => {
 157                 assert!(last_min_end <= position);
 158                 position - last_min_end
 159             }
 160         };
 161         self.lazy_state = LazyState::Previous(min_end);
 162         self.emit_usize(distance)
 163     }
 164
 165     pub fn lazy<T: Encodable>(&mut self, value: &T) -> Lazy<T> {
 166         self.emit_node(|ecx, pos| {
 167             value.encode(ecx).unwrap();
 168
 169             assert!(pos + Lazy::<T>::min_size() <= ecx.position());
 170             Lazy::with_position(pos)
 171         })
 172     }
 173
 174     fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T>
 175         where I: IntoIterator<Item = T>,
 176               T: Encodable
 177     {
 178         self.emit_node(|ecx, pos| {
 179             let len = iter.into_iter().map(|value| value.encode(ecx).unwrap()).count();
 180
 181             assert!(pos + LazySeq::<T>::min_size(len) <= ecx.position());
 182             LazySeq::with_position_and_length(pos, len)
 183         })
 184     }
 185
 186     fn lazy_seq_ref<'b, I, T>(&mut self, iter: I) -> LazySeq<T>
 187         where I: IntoIterator<Item = &'b T>,
 188               T: 'b + Encodable
 189     {
 190         self.emit_node(|ecx, pos| {
 191             let len = iter.into_iter().map(|value| value.encode(ecx).unwrap()).count();
 192
 193             assert!(pos + LazySeq::<T>::min_size(len) <= ecx.position());
 194             LazySeq::with_position_and_length(pos, len)
 195         })
 196     }
 197
 198     /// Encode the given value or a previously cached shorthand.
 199     fn encode_with_shorthand<T, U, M>(&mut self,
 200                                       value: &T,
 201                                       variant: &U,
 202                                       map: M)
 203                                       -> Result<(), <Self as Encoder>::Error>
 204         where M: for<'b> Fn(&'b mut Self) -> &'b mut FxHashMap<T, usize>,
 205               T: Clone + Eq + Hash,
 206               U: Encodable
 207     {
 208         let existing_shorthand = map(self).get(value).cloned();
 209         if let Some(shorthand) = existing_shorthand {
 210             return self.emit_usize(shorthand);
 211         }
 212
 213         let start = self.position();
 214         variant.encode(self)?;
 215         let len = self.position() - start;
 216
 217         // The shorthand encoding uses the same usize as the
 218         // discriminant, with an offset so they can't conflict.
 219         let discriminant = unsafe { intrinsics::discriminant_value(variant) };
 220         assert!(discriminant < SHORTHAND_OFFSET as u64);
 221         let shorthand = start + SHORTHAND_OFFSET;
 222
 223         // Get the number of bits that leb128 could fit
 224         // in the same space as the fully encoded type.
 225         let leb128_bits = len * 7;
 226
 227         // Check that the shorthand is a not longer than the
 228         // full encoding itself, i.e. it's an obvious win.
 229         if leb128_bits >= 64 || (shorthand as u64) < (1 << leb128_bits) {
 230             map(self).insert(value.clone(), shorthand);
 231         }
 232
 233         Ok(())
 234     }
 235
 236     /// For every DefId that we create a metadata item for, we include a
 237     /// serialized copy of its DefKey, which allows us to recreate a path.
 238     fn encode_def_key(&mut self, def_id: DefId) -> Lazy<hir::map::DefKey> {
 239         let tcx = self.tcx;
 240         self.lazy(&tcx.map.def_key(def_id))
 241     }
 242
 243     fn encode_item_variances(&mut self, def_id: DefId) -> LazySeq<ty::Variance> {
 244         let tcx = self.tcx;
 245         self.lazy_seq(tcx.item_variances(def_id).iter().cloned())
 246     }
 247
 248     fn encode_item_type(&mut self, def_id: DefId) -> Lazy<Ty<'tcx>> {
 249         let tcx = self.tcx;
 250         self.lazy(&tcx.item_type(def_id))
 251     }
 252
 253     /// Encode data for the given variant of the given ADT. The
 254     /// index of the variant is untracked: this is ok because we
 255     /// will have to lookup the adt-def by its id, and that gives us
 256     /// the right to access any information in the adt-def (including,
 257     /// e.g., the length of the various vectors).
 258     fn encode_enum_variant_info(&mut self,
 259                                 (enum_did, Untracked(index)): (DefId, Untracked<usize>))
 260                                 -> Entry<'tcx> {
 261         let tcx = self.tcx;
 262         let def = tcx.lookup_adt_def(enum_did);
 263         let variant = &def.variants[index];
 264         let def_id = variant.did;
 265
 266         let data = VariantData {
 267             ctor_kind: variant.ctor_kind,
 268             disr: variant.disr_val.to_u64_unchecked(),
 269             struct_ctor: None,
 270         };
 271
 272         let enum_id = tcx.map.as_local_node_id(enum_did).unwrap();
 273         let enum_vis = &tcx.map.expect_item(enum_id).vis;
 274
 275         Entry {
 276             kind: EntryKind::Variant(self.lazy(&data)),
 277             visibility: enum_vis.simplify(),
 278             def_key: self.encode_def_key(def_id),
 279             attributes: self.encode_attributes(&tcx.get_attrs(def_id)),
 280             children: self.lazy_seq(variant.fields.iter().map(|f| {
 281                 assert!(f.did.is_local());
 282                 f.did.index
 283             })),
 284             stability: self.encode_stability(def_id),
 285             deprecation: self.encode_deprecation(def_id),
 286
 287             ty: Some(self.encode_item_type(def_id)),
 288             inherent_impls: LazySeq::empty(),
 289             variances: LazySeq::empty(),
 290             generics: Some(self.encode_generics(def_id)),
 291             predicates: Some(self.encode_predicates(def_id)),
 292
 293             ast: None,
 294             mir: None,
 295         }
 296     }
 297
 298     fn encode_info_for_mod(&mut self,
 299                            FromId(id, (md, attrs, vis)): FromId<(&hir::Mod,
 300                                                                  &[ast::Attribute],
 301                                                                  &hir::Visibility)>)
 302                            -> Entry<'tcx> {
 303         let tcx = self.tcx;
 304         let def_id = tcx.map.local_def_id(id);
 305
 306         let data = ModData {
 307             reexports: match self.reexports.get(&id) {
 308                 Some(exports) if *vis == hir::Public => self.lazy_seq_ref(exports),
 309                 _ => LazySeq::empty(),
 310             },
 311         };
 312
 313         Entry {
 314             kind: EntryKind::Mod(self.lazy(&data)),
 315             visibility: vis.simplify(),
 316             def_key: self.encode_def_key(def_id),
 317             attributes: self.encode_attributes(attrs),
 318             children: self.lazy_seq(md.item_ids.iter().map(|item_id| {
 319                 tcx.map.local_def_id(item_id.id).index
 320             })),
 321             stability: self.encode_stability(def_id),
 322             deprecation: self.encode_deprecation(def_id),
 323
 324             ty: None,
 325             inherent_impls: LazySeq::empty(),
 326             variances: LazySeq::empty(),
 327             generics: None,
 328             predicates: None,
 329
 330             ast: None,
 331             mir: None
 332         }
 333     }
 334 }
 335
 336 trait Visibility {
 337     fn simplify(&self) -> ty::Visibility;
 338 }
 339
 340 impl Visibility for hir::Visibility {
 341     fn simplify(&self) -> ty::Visibility {
 342         if *self == hir::Public {
 343             ty::Visibility::Public
 344         } else {
 345             ty::Visibility::PrivateExternal
 346         }
 347     }
 348 }
 349
 350 impl Visibility for ty::Visibility {
 351     fn simplify(&self) -> ty::Visibility {
 352         if *self == ty::Visibility::Public {
 353             ty::Visibility::Public
 354         } else {
 355             ty::Visibility::PrivateExternal
 356         }
 357     }
 358 }
 359
 360 impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
 361     fn encode_fields(&mut self, adt_def_id: DefId) {
 362         let def = self.tcx.lookup_adt_def(adt_def_id);
 363         for (variant_index, variant) in def.variants.iter().enumerate() {
 364             for (field_index, field) in variant.fields.iter().enumerate() {
 365                 self.record(field.did,
 366                             EncodeContext::encode_field,
 367                             (adt_def_id, Untracked((variant_index, field_index))));
 368             }
 369         }
 370     }
 371 }
 372
 373 impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 374     /// Encode data for the given field of the given variant of the
 375     /// given ADT. The indices of the variant/field are untracked:
 376     /// this is ok because we will have to lookup the adt-def by its
 377     /// id, and that gives us the right to access any information in
 378     /// the adt-def (including, e.g., the length of the various
 379     /// vectors).
 380     fn encode_field(&mut self,
 381                     (adt_def_id, Untracked((variant_index, field_index))): (DefId,
 382                                                                             Untracked<(usize,
 383                                                                                        usize)>))
 384                     -> Entry<'tcx> {
 385         let tcx = self.tcx;
 386         let variant = &tcx.lookup_adt_def(adt_def_id).variants[variant_index];
 387         let field = &variant.fields[field_index];
 388
 389         let def_id = field.did;
 390         let variant_id = tcx.map.as_local_node_id(variant.did).unwrap();
 391         let variant_data = tcx.map.expect_variant_data(variant_id);
 392
 393         Entry {
 394             kind: EntryKind::Field,
 395             visibility: field.vis.simplify(),
 396             def_key: self.encode_def_key(def_id),
 397             attributes: self.encode_attributes(&variant_data.fields()[field_index].attrs),
 398             children: LazySeq::empty(),
 399             stability: self.encode_stability(def_id),
 400             deprecation: self.encode_deprecation(def_id),
 401
 402             ty: Some(self.encode_item_type(def_id)),
 403             inherent_impls: LazySeq::empty(),
 404             variances: LazySeq::empty(),
 405             generics: Some(self.encode_generics(def_id)),
 406             predicates: Some(self.encode_predicates(def_id)),
 407
 408             ast: None,
 409             mir: None,
 410         }
 411     }
 412
 413     fn encode_struct_ctor(&mut self, (adt_def_id, def_id): (DefId, DefId)) -> Entry<'tcx> {
 414         let tcx = self.tcx;
 415         let variant = tcx.lookup_adt_def(adt_def_id).struct_variant();
 416
 417         let data = VariantData {
 418             ctor_kind: variant.ctor_kind,
 419             disr: variant.disr_val.to_u64_unchecked(),
 420             struct_ctor: Some(def_id.index),
 421         };
 422
 423         let struct_id = tcx.map.as_local_node_id(adt_def_id).unwrap();
 424         let struct_vis = &tcx.map.expect_item(struct_id).vis;
 425
 426         Entry {
 427             kind: EntryKind::Struct(self.lazy(&data)),
 428             visibility: struct_vis.simplify(),
 429             def_key: self.encode_def_key(def_id),
 430             attributes: LazySeq::empty(),
 431             children: LazySeq::empty(),
 432             stability: self.encode_stability(def_id),
 433             deprecation: self.encode_deprecation(def_id),
 434
 435             ty: Some(self.encode_item_type(def_id)),
 436             inherent_impls: LazySeq::empty(),
 437             variances: LazySeq::empty(),
 438             generics: Some(self.encode_generics(def_id)),
 439             predicates: Some(self.encode_predicates(def_id)),
 440
 441             ast: None,
 442             mir: None,
 443         }
 444     }
 445
 446     fn encode_generics(&mut self, def_id: DefId) -> Lazy<ty::Generics<'tcx>> {
 447         let tcx = self.tcx;
 448         self.lazy(tcx.item_generics(def_id))
 449     }
 450
 451     fn encode_predicates(&mut self, def_id: DefId) -> Lazy<ty::GenericPredicates<'tcx>> {
 452         let tcx = self.tcx;
 453         self.lazy(&tcx.item_predicates(def_id))
 454     }
 455
 456     fn encode_info_for_trait_item(&mut self, def_id: DefId) -> Entry<'tcx> {
 457         let tcx = self.tcx;
 458
 459         let node_id = tcx.map.as_local_node_id(def_id).unwrap();
 460         let ast_item = tcx.map.expect_trait_item(node_id);
 461         let trait_item = tcx.associated_item(def_id);
 462
 463         let container = match trait_item.defaultness {
 464             hir::Defaultness::Default { has_value: true } =>
 465                 AssociatedContainer::TraitWithDefault,
 466             hir::Defaultness::Default { has_value: false } =>
 467                 AssociatedContainer::TraitRequired,
 468             hir::Defaultness::Final =>
 469                 span_bug!(ast_item.span, "traits cannot have final items"),
 470         };
 471
 472         let kind = match trait_item.kind {
 473             ty::AssociatedKind::Const => EntryKind::AssociatedConst(container),
 474             ty::AssociatedKind::Method => {
 475                 let fn_data = if let hir::MethodTraitItem(ref sig, _) = ast_item.node {
 476                     FnData {
 477                         constness: hir::Constness::NotConst,
 478                         arg_names: self.encode_fn_arg_names(&sig.decl),
 479                     }
 480                 } else {
 481                     bug!()
 482                 };
 483                 EntryKind::Method(self.lazy(&MethodData {
 484                     fn_data: fn_data,
 485                     container: container,
 486                     has_self: trait_item.method_has_self_argument,
 487                 }))
 488             }
 489             ty::AssociatedKind::Type => EntryKind::AssociatedType(container),
 490         };
 491
 492         Entry {
 493             kind: kind,
 494             visibility: trait_item.vis.simplify(),
 495             def_key: self.encode_def_key(def_id),
 496             attributes: self.encode_attributes(&ast_item.attrs),
 497             children: LazySeq::empty(),
 498             stability: self.encode_stability(def_id),
 499             deprecation: self.encode_deprecation(def_id),
 500
 501             ty: match trait_item.kind {
 502                 ty::AssociatedKind::Const |
 503                 ty::AssociatedKind::Method => {
 504                     Some(self.encode_item_type(def_id))
 505                 }
 506                 ty::AssociatedKind::Type => {
 507                     if trait_item.defaultness.has_value() {
 508                         Some(self.encode_item_type(def_id))
 509                     } else {
 510                         None
 511                     }
 512                 }
 513             },
 514             inherent_impls: LazySeq::empty(),
 515             variances: LazySeq::empty(),
 516             generics: Some(self.encode_generics(def_id)),
 517             predicates: Some(self.encode_predicates(def_id)),
 518
 519             ast: if trait_item.kind == ty::AssociatedKind::Const {
 520                 let trait_def_id = trait_item.container.id();
 521                 Some(self.encode_inlined_item(InlinedItemRef::TraitItem(trait_def_id, ast_item)))
 522             } else {
 523                 None
 524             },
 525             mir: self.encode_mir(def_id),
 526         }
 527     }
 528
 529     fn encode_info_for_impl_item(&mut self, def_id: DefId) -> Entry<'tcx> {
 530         let node_id = self.tcx.map.as_local_node_id(def_id).unwrap();
 531         let ast_item = self.tcx.map.expect_impl_item(node_id);
 532         let impl_item = self.tcx.associated_item(def_id);
 533         let impl_def_id = impl_item.container.id();
 534
 535         let container = match impl_item.defaultness {
 536             hir::Defaultness::Default { has_value: true } => AssociatedContainer::ImplDefault,
 537             hir::Defaultness::Final => AssociatedContainer::ImplFinal,
 538             hir::Defaultness::Default { has_value: false } =>
 539                 span_bug!(ast_item.span, "impl items always have values (currently)"),
 540         };
 541
 542         let kind = match impl_item.kind {
 543             ty::AssociatedKind::Const => EntryKind::AssociatedConst(container),
 544             ty::AssociatedKind::Method => {
 545                 let fn_data = if let hir::ImplItemKind::Method(ref sig, _) = ast_item.node {
 546                     FnData {
 547                         constness: sig.constness,
 548                         arg_names: self.encode_fn_arg_names(&sig.decl),
 549                     }
 550                 } else {
 551                     bug!()
 552                 };
 553                 EntryKind::Method(self.lazy(&MethodData {
 554                     fn_data: fn_data,
 555                     container: container,
 556                     has_self: impl_item.method_has_self_argument,
 557                 }))
 558             }
 559             ty::AssociatedKind::Type => EntryKind::AssociatedType(container)
 560         };
 561
 562         let (ast, mir) = if impl_item.kind == ty::AssociatedKind::Const {
 563             (true, true)
 564         } else if let hir::ImplItemKind::Method(ref sig, _) = ast_item.node {
 565             let generics = self.tcx.item_generics(def_id);
 566             let types = generics.parent_types as usize + generics.types.len();
 567             let needs_inline = types > 0 || attr::requests_inline(&ast_item.attrs);
 568             let is_const_fn = sig.constness == hir::Constness::Const;
 569             (is_const_fn, needs_inline || is_const_fn)
 570         } else {
 571             (false, false)
 572         };
 573
 574         Entry {
 575             kind: kind,
 576             visibility: impl_item.vis.simplify(),
 577             def_key: self.encode_def_key(def_id),
 578             attributes: self.encode_attributes(&ast_item.attrs),
 579             children: LazySeq::empty(),
 580             stability: self.encode_stability(def_id),
 581             deprecation: self.encode_deprecation(def_id),
 582
 583             ty: Some(self.encode_item_type(def_id)),
 584             inherent_impls: LazySeq::empty(),
 585             variances: LazySeq::empty(),
 586             generics: Some(self.encode_generics(def_id)),
 587             predicates: Some(self.encode_predicates(def_id)),
 588
 589             ast: if ast {
 590                 Some(self.encode_inlined_item(InlinedItemRef::ImplItem(impl_def_id, ast_item)))
 591             } else {
 592                 None
 593             },
 594             mir: if mir { self.encode_mir(def_id) } else { None },
 595         }
 596     }
 597
 598     fn encode_fn_arg_names(&mut self, decl: &hir::FnDecl) -> LazySeq<ast::Name> {
 599         self.lazy_seq(decl.inputs.iter().map(|arg| {
 600             if let PatKind::Binding(_, ref path1, _) = arg.pat.node {
 601                 path1.node
 602             } else {
 603                 Symbol::intern("")
 604             }
 605         }))
 606     }
 607
 608     fn encode_mir(&mut self, def_id: DefId) -> Option<Lazy<mir::Mir<'tcx>>> {
 609         self.tcx.mir_map.borrow().get(&def_id).map(|mir| self.lazy(&*mir.borrow()))
 610     }
 611
 612     // Encodes the inherent implementations of a structure, enumeration, or trait.
 613     fn encode_inherent_implementations(&mut self, def_id: DefId) -> LazySeq<DefIndex> {
 614         match self.tcx.inherent_impls.borrow().get(&def_id) {
 615             None => LazySeq::empty(),
 616             Some(implementations) => {
 617                 self.lazy_seq(implementations.iter().map(|&def_id| {
 618                     assert!(def_id.is_local());
 619                     def_id.index
 620                 }))
 621             }
 622         }
 623     }
 624
 625     fn encode_stability(&mut self, def_id: DefId) -> Option<Lazy<attr::Stability>> {
 626         self.tcx.lookup_stability(def_id).map(|stab| self.lazy(stab))
 627     }
 628
 629     fn encode_deprecation(&mut self, def_id: DefId) -> Option<Lazy<attr::Deprecation>> {
 630         self.tcx.lookup_deprecation(def_id).map(|depr| self.lazy(&depr))
 631     }
 632
 633     fn encode_info_for_item(&mut self, (def_id, item): (DefId, &hir::Item)) -> Entry<'tcx> {
 634         let tcx = self.tcx;
 635
 636         debug!("encoding info for item at {}",
 637                tcx.sess.codemap().span_to_string(item.span));
 638
 639         let kind = match item.node {
 640             hir::ItemStatic(_, hir::MutMutable, _) => EntryKind::MutStatic,
 641             hir::ItemStatic(_, hir::MutImmutable, _) => EntryKind::ImmStatic,
 642             hir::ItemConst(..) => EntryKind::Const,
 643             hir::ItemFn(ref decl, _, constness, ..) => {
 644                 let data = FnData {
 645                     constness: constness,
 646                     arg_names: self.encode_fn_arg_names(&decl),
 647                 };
 648
 649                 EntryKind::Fn(self.lazy(&data))
 650             }
 651             hir::ItemMod(ref m) => {
 652                 return self.encode_info_for_mod(FromId(item.id, (m, &item.attrs, &item.vis)));
 653             }
 654             hir::ItemForeignMod(_) => EntryKind::ForeignMod,
 655             hir::ItemTy(..) => EntryKind::Type,
 656             hir::ItemEnum(..) => EntryKind::Enum,
 657             hir::ItemStruct(ref struct_def, _) => {
 658                 let variant = tcx.lookup_adt_def(def_id).struct_variant();
 659
 660                 // Encode def_ids for each field and method
 661                 // for methods, write all the stuff get_trait_method
 662                 // needs to know
 663                 let struct_ctor = if !struct_def.is_struct() {
 664                     Some(tcx.map.local_def_id(struct_def.id()).index)
 665                 } else {
 666                     None
 667                 };
 668                 EntryKind::Struct(self.lazy(&VariantData {
 669                     ctor_kind: variant.ctor_kind,
 670                     disr: variant.disr_val.to_u64_unchecked(),
 671                     struct_ctor: struct_ctor,
 672                 }))
 673             }
 674             hir::ItemUnion(..) => {
 675                 let variant = tcx.lookup_adt_def(def_id).struct_variant();
 676
 677                 EntryKind::Union(self.lazy(&VariantData {
 678                     ctor_kind: variant.ctor_kind,
 679                     disr: variant.disr_val.to_u64_unchecked(),
 680                     struct_ctor: None,
 681                 }))
 682             }
 683             hir::ItemDefaultImpl(..) => {
 684                 let data = ImplData {
 685                     polarity: hir::ImplPolarity::Positive,
 686                     parent_impl: None,
 687                     coerce_unsized_kind: None,
 688                     trait_ref: tcx.impl_trait_ref(def_id).map(|trait_ref| self.lazy(&trait_ref)),
 689                 };
 690
 691                 EntryKind::DefaultImpl(self.lazy(&data))
 692             }
 693             hir::ItemImpl(_, polarity, ..) => {
 694                 let trait_ref = tcx.impl_trait_ref(def_id);
 695                 let parent = if let Some(trait_ref) = trait_ref {
 696                     let trait_def = tcx.lookup_trait_def(trait_ref.def_id);
 697                     trait_def.ancestors(def_id).skip(1).next().and_then(|node| {
 698                         match node {
 699                             specialization_graph::Node::Impl(parent) => Some(parent),
 700                             _ => None,
 701                         }
 702                     })
 703                 } else {
 704                     None
 705                 };
 706
 707                 let data = ImplData {
 708                     polarity: polarity,
 709                     parent_impl: parent,
 710                     coerce_unsized_kind: tcx.custom_coerce_unsized_kinds
 711                         .borrow()
 712                         .get(&def_id)
 713                         .cloned(),
 714                     trait_ref: trait_ref.map(|trait_ref| self.lazy(&trait_ref)),
 715                 };
 716
 717                 EntryKind::Impl(self.lazy(&data))
 718             }
 719             hir::ItemTrait(..) => {
 720                 let trait_def = tcx.lookup_trait_def(def_id);
 721                 let data = TraitData {
 722                     unsafety: trait_def.unsafety,
 723                     paren_sugar: trait_def.paren_sugar,
 724                     has_default_impl: tcx.trait_has_default_impl(def_id),
 725                     trait_ref: self.lazy(&trait_def.trait_ref),
 726                     super_predicates: self.lazy(&tcx.item_super_predicates(def_id)),
 727                 };
 728
 729                 EntryKind::Trait(self.lazy(&data))
 730             }
 731             hir::ItemExternCrate(_) |
 732             hir::ItemUse(_) => bug!("cannot encode info for item {:?}", item),
 733         };
 734
 735         Entry {
 736             kind: kind,
 737             visibility: item.vis.simplify(),
 738             def_key: self.encode_def_key(def_id),
 739             attributes: self.encode_attributes(&item.attrs),
 740             children: match item.node {
 741                 hir::ItemForeignMod(ref fm) => {
 742                     self.lazy_seq(fm.items
 743                         .iter()
 744                         .map(|foreign_item| tcx.map.local_def_id(foreign_item.id).index))
 745                 }
 746                 hir::ItemEnum(..) => {
 747                     let def = self.tcx.lookup_adt_def(def_id);
 748                     self.lazy_seq(def.variants.iter().map(|v| {
 749                         assert!(v.did.is_local());
 750                         v.did.index
 751                     }))
 752                 }
 753                 hir::ItemStruct(..) |
 754                 hir::ItemUnion(..) => {
 755                     let def = self.tcx.lookup_adt_def(def_id);
 756                     self.lazy_seq(def.struct_variant().fields.iter().map(|f| {
 757                         assert!(f.did.is_local());
 758                         f.did.index
 759                     }))
 760                 }
 761                 hir::ItemImpl(..) |
 762                 hir::ItemTrait(..) => {
 763                     self.lazy_seq(tcx.associated_item_def_ids(def_id).iter().map(|&def_id| {
 764                         assert!(def_id.is_local());
 765                         def_id.index
 766                     }))
 767                 }
 768                 _ => LazySeq::empty(),
 769             },
 770             stability: self.encode_stability(def_id),
 771             deprecation: self.encode_deprecation(def_id),
 772
 773             ty: match item.node {
 774                 hir::ItemStatic(..) |
 775                 hir::ItemConst(..) |
 776                 hir::ItemFn(..) |
 777                 hir::ItemTy(..) |
 778                 hir::ItemEnum(..) |
 779                 hir::ItemStruct(..) |
 780                 hir::ItemUnion(..) |
 781                 hir::ItemImpl(..) => Some(self.encode_item_type(def_id)),
 782                 _ => None,
 783             },
 784             inherent_impls: self.encode_inherent_implementations(def_id),
 785             variances: match item.node {
 786                 hir::ItemEnum(..) |
 787                 hir::ItemStruct(..) |
 788                 hir::ItemUnion(..) |
 789                 hir::ItemTrait(..) => self.encode_item_variances(def_id),
 790                 _ => LazySeq::empty(),
 791             },
 792             generics: match item.node {
 793                 hir::ItemStatic(..) |
 794                 hir::ItemConst(..) |
 795                 hir::ItemFn(..) |
 796                 hir::ItemTy(..) |
 797                 hir::ItemEnum(..) |
 798                 hir::ItemStruct(..) |
 799                 hir::ItemUnion(..) |
 800                 hir::ItemImpl(..) |
 801                 hir::ItemTrait(..) => Some(self.encode_generics(def_id)),
 802                 _ => None,
 803             },
 804             predicates: match item.node {
 805                 hir::ItemStatic(..) |
 806                 hir::ItemConst(..) |
 807                 hir::ItemFn(..) |
 808                 hir::ItemTy(..) |
 809                 hir::ItemEnum(..) |
 810                 hir::ItemStruct(..) |
 811                 hir::ItemUnion(..) |
 812                 hir::ItemImpl(..) |
 813                 hir::ItemTrait(..) => Some(self.encode_predicates(def_id)),
 814                 _ => None,
 815             },
 816
 817             ast: match item.node {
 818                 hir::ItemConst(..) |
 819                 hir::ItemFn(_, _, hir::Constness::Const, ..) => {
 820                     Some(self.encode_inlined_item(InlinedItemRef::Item(def_id, item)))
 821                 }
 822                 _ => None,
 823             },
 824             mir: match item.node {
 825                 hir::ItemConst(..) => self.encode_mir(def_id),
 826                 hir::ItemFn(_, _, constness, _, ref generics, _) => {
 827                     let tps_len = generics.ty_params.len();
 828                     let needs_inline = tps_len > 0 || attr::requests_inline(&item.attrs);
 829                     if needs_inline || constness == hir::Constness::Const {
 830                         self.encode_mir(def_id)
 831                     } else {
 832                         None
 833                     }
 834                 }
 835                 _ => None,
 836             },
 837         }
 838     }
 839
 840     /// Serialize the text of exported macros
 841     fn encode_info_for_macro_def(&mut self, macro_def: &hir::MacroDef) -> Entry<'tcx> {
 842         let def_id = self.tcx.map.local_def_id(macro_def.id);
 843         let macro_def = MacroDef {
 844             name: macro_def.name,
 845             attrs: macro_def.attrs.to_vec(),
 846             span: macro_def.span,
 847             body: ::syntax::print::pprust::tts_to_string(&macro_def.body)
 848         };
 849         Entry {
 850             kind: EntryKind::MacroDef(self.lazy(&macro_def)),
 851             visibility: ty::Visibility::Public,
 852             def_key: self.encode_def_key(def_id),
 853
 854             attributes: LazySeq::empty(),
 855             children: LazySeq::empty(),
 856             stability: None,
 857             deprecation: None,
 858             ty: None,
 859             inherent_impls: LazySeq::empty(),
 860             variances: LazySeq::empty(),
 861             generics: None,
 862             predicates: None,
 863             ast: None,
 864             mir: None,
 865         }
 866     }
 867 }
 868
 869 impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
 870     /// In some cases, along with the item itself, we also
 871     /// encode some sub-items. Usually we want some info from the item
 872     /// so it's easier to do that here then to wait until we would encounter
 873     /// normally in the visitor walk.
 874     fn encode_addl_info_for_item(&mut self, item: &hir::Item) {
 875         let def_id = self.tcx.map.local_def_id(item.id);
 876         match item.node {
 877             hir::ItemStatic(..) |
 878             hir::ItemConst(..) |
 879             hir::ItemFn(..) |
 880             hir::ItemMod(..) |
 881             hir::ItemForeignMod(..) |
 882             hir::ItemExternCrate(..) |
 883             hir::ItemUse(..) |
 884             hir::ItemDefaultImpl(..) |
 885             hir::ItemTy(..) => {
 886                 // no sub-item recording needed in these cases
 887             }
 888             hir::ItemEnum(..) => {
 889                 self.encode_fields(def_id);
 890
 891                 let def = self.tcx.lookup_adt_def(def_id);
 892                 for (i, variant) in def.variants.iter().enumerate() {
 893                     self.record(variant.did,
 894                                 EncodeContext::encode_enum_variant_info,
 895                                 (def_id, Untracked(i)));
 896                 }
 897             }
 898             hir::ItemStruct(ref struct_def, _) => {
 899                 self.encode_fields(def_id);
 900
 901                 // If the struct has a constructor, encode it.
 902                 if !struct_def.is_struct() {
 903                     let ctor_def_id = self.tcx.map.local_def_id(struct_def.id());
 904                     self.record(ctor_def_id,
 905                                 EncodeContext::encode_struct_ctor,
 906                                 (def_id, ctor_def_id));
 907                 }
 908             }
 909             hir::ItemUnion(..) => {
 910                 self.encode_fields(def_id);
 911             }
 912             hir::ItemImpl(..) => {
 913                 for &trait_item_def_id in &self.tcx.associated_item_def_ids(def_id)[..] {
 914                     self.record(trait_item_def_id,
 915                                 EncodeContext::encode_info_for_impl_item,
 916                                 trait_item_def_id);
 917                 }
 918             }
 919             hir::ItemTrait(..) => {
 920                 for &item_def_id in &self.tcx.associated_item_def_ids(def_id)[..] {
 921                     self.record(item_def_id,
 922                                 EncodeContext::encode_info_for_trait_item,
 923                                 item_def_id);
 924                 }
 925             }
 926         }
 927     }
 928 }
 929
 930 impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 931     fn encode_info_for_foreign_item(&mut self,
 932                                     (def_id, nitem): (DefId, &hir::ForeignItem))
 933                                     -> Entry<'tcx> {
 934         let tcx = self.tcx;
 935
 936         debug!("writing foreign item {}", tcx.node_path_str(nitem.id));
 937
 938         let kind = match nitem.node {
 939             hir::ForeignItemFn(ref fndecl, _) => {
 940                 let data = FnData {
 941                     constness: hir::Constness::NotConst,
 942                     arg_names: self.encode_fn_arg_names(&fndecl),
 943                 };
 944                 EntryKind::ForeignFn(self.lazy(&data))
 945             }
 946             hir::ForeignItemStatic(_, true) => EntryKind::ForeignMutStatic,
 947             hir::ForeignItemStatic(_, false) => EntryKind::ForeignImmStatic,
 948         };
 949
 950         Entry {
 951             kind: kind,
 952             visibility: nitem.vis.simplify(),
 953             def_key: self.encode_def_key(def_id),
 954             attributes: self.encode_attributes(&nitem.attrs),
 955             children: LazySeq::empty(),
 956             stability: self.encode_stability(def_id),
 957             deprecation: self.encode_deprecation(def_id),
 958
 959             ty: Some(self.encode_item_type(def_id)),
 960             inherent_impls: LazySeq::empty(),
 961             variances: LazySeq::empty(),
 962             generics: Some(self.encode_generics(def_id)),
 963             predicates: Some(self.encode_predicates(def_id)),
 964
 965             ast: None,
 966             mir: None,
 967         }
 968     }
 969 }
 970
 971 struct EncodeVisitor<'a, 'b: 'a, 'tcx: 'b> {
 972     index: IndexBuilder<'a, 'b, 'tcx>,
 973 }
 974
 975 impl<'a, 'b, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'tcx> {
 976     fn visit_expr(&mut self, ex: &'tcx hir::Expr) {
 977         intravisit::walk_expr(self, ex);
 978         self.index.encode_info_for_expr(ex);
 979     }
 980     fn visit_item(&mut self, item: &'tcx hir::Item) {
 981         intravisit::walk_item(self, item);
 982         let def_id = self.index.tcx.map.local_def_id(item.id);
 983         match item.node {
 984             hir::ItemExternCrate(_) |
 985             hir::ItemUse(_) => (), // ignore these
 986             _ => self.index.record(def_id, EncodeContext::encode_info_for_item, (def_id, item)),
 987         }
 988         self.index.encode_addl_info_for_item(item);
 989     }
 990     fn visit_foreign_item(&mut self, ni: &'tcx hir::ForeignItem) {
 991         intravisit::walk_foreign_item(self, ni);
 992         let def_id = self.index.tcx.map.local_def_id(ni.id);
 993         self.index.record(def_id,
 994                           EncodeContext::encode_info_for_foreign_item,
 995                           (def_id, ni));
 996     }
 997     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 998         intravisit::walk_ty(self, ty);
 999         self.index.encode_info_for_ty(ty);
1000     }
1001     fn visit_macro_def(&mut self, macro_def: &'tcx hir::MacroDef) {
1002         let def_id = self.index.tcx.map.local_def_id(macro_def.id);
1003         self.index.record(def_id, EncodeContext::encode_info_for_macro_def, macro_def);
1004     }
1005 }
1006
1007 impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
1008     fn encode_info_for_ty(&mut self, ty: &hir::Ty) {
1009         if let hir::TyImplTrait(_) = ty.node {
1010             let def_id = self.tcx.map.local_def_id(ty.id);
1011             self.record(def_id, EncodeContext::encode_info_for_anon_ty, def_id);
1012         }
1013     }
1014
1015     fn encode_info_for_expr(&mut self, expr: &hir::Expr) {
1016         match expr.node {
1017             hir::ExprClosure(..) => {
1018                 let def_id = self.tcx.map.local_def_id(expr.id);
1019                 self.record(def_id, EncodeContext::encode_info_for_closure, def_id);
1020             }
1021             _ => {}
1022         }
1023     }
1024 }
1025
1026 impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
1027     fn encode_info_for_anon_ty(&mut self, def_id: DefId) -> Entry<'tcx> {
1028         Entry {
1029             kind: EntryKind::Type,
1030             visibility: ty::Visibility::Public,
1031             def_key: self.encode_def_key(def_id),
1032             attributes: LazySeq::empty(),
1033             children: LazySeq::empty(),
1034             stability: None,
1035             deprecation: None,
1036
1037             ty: Some(self.encode_item_type(def_id)),
1038             inherent_impls: LazySeq::empty(),
1039             variances: LazySeq::empty(),
1040             generics: Some(self.encode_generics(def_id)),
1041             predicates: Some(self.encode_predicates(def_id)),
1042
1043             ast: None,
1044             mir: None,
1045         }
1046     }
1047
1048     fn encode_info_for_closure(&mut self, def_id: DefId) -> Entry<'tcx> {
1049         let tcx = self.tcx;
1050
1051         let data = ClosureData {
1052             kind: tcx.closure_kind(def_id),
1053             ty: self.lazy(&tcx.tables().closure_tys[&def_id]),
1054         };
1055
1056         Entry {
1057             kind: EntryKind::Closure(self.lazy(&data)),
1058             visibility: ty::Visibility::Public,
1059             def_key: self.encode_def_key(def_id),
1060             attributes: self.encode_attributes(&tcx.get_attrs(def_id)),
1061             children: LazySeq::empty(),
1062             stability: None,
1063             deprecation: None,
1064
1065             ty: Some(self.encode_item_type(def_id)),
1066             inherent_impls: LazySeq::empty(),
1067             variances: LazySeq::empty(),
1068             generics: Some(self.encode_generics(def_id)),
1069             predicates: None,
1070
1071             ast: None,
1072             mir: self.encode_mir(def_id),
1073         }
1074     }
1075
1076     fn encode_info_for_items(&mut self) -> Index {
1077         let krate = self.tcx.map.krate();
1078         let mut index = IndexBuilder::new(self);
1079         index.record(DefId::local(CRATE_DEF_INDEX),
1080                      EncodeContext::encode_info_for_mod,
1081                      FromId(CRATE_NODE_ID, (&krate.module, &krate.attrs, &hir::Public)));
1082         let mut visitor = EncodeVisitor { index: index };
1083         krate.visit_all_item_likes(&mut visitor.as_deep_visitor());
1084         for macro_def in &krate.exported_macros {
1085             visitor.visit_macro_def(macro_def);
1086         }
1087         visitor.index.into_items()
1088     }
1089
1090     fn encode_attributes(&mut self, attrs: &[ast::Attribute]) -> LazySeq<ast::Attribute> {
1091         self.lazy_seq_ref(attrs)
1092     }
1093
1094     fn encode_crate_deps(&mut self) -> LazySeq<CrateDep> {
1095         fn get_ordered_deps(cstore: &cstore::CStore) -> Vec<(CrateNum, Rc<cstore::CrateMetadata>)> {
1096             // Pull the cnums and name,vers,hash out of cstore
1097             let mut deps = Vec::new();
1098             cstore.iter_crate_data(|cnum, val| {
1099                 deps.push((cnum, val.clone()));
1100             });
1101
1102             // Sort by cnum
1103             deps.sort_by(|kv1, kv2| kv1.0.cmp(&kv2.0));
1104
1105             // Sanity-check the crate numbers
1106             let mut expected_cnum = 1;
1107             for &(n, _) in &deps {
1108                 assert_eq!(n, CrateNum::new(expected_cnum));
1109                 expected_cnum += 1;
1110             }
1111
1112             deps
1113         }
1114
1115         // We're just going to write a list of crate 'name-hash-version's, with
1116         // the assumption that they are numbered 1 to n.
1117         // FIXME (#2166): This is not nearly enough to support correct versioning
1118         // but is enough to get transitive crate dependencies working.
1119         let deps = get_ordered_deps(self.cstore);
1120         self.lazy_seq(deps.iter().map(|&(_, ref dep)| {
1121             CrateDep {
1122                 name: dep.name(),
1123                 hash: dep.hash(),
1124                 kind: dep.dep_kind.get(),
1125             }
1126         }))
1127     }
1128
1129     fn encode_lang_items(&mut self) -> (LazySeq<(DefIndex, usize)>, LazySeq<lang_items::LangItem>) {
1130         let tcx = self.tcx;
1131         let lang_items = tcx.lang_items.items().iter();
1132         (self.lazy_seq(lang_items.enumerate().filter_map(|(i, &opt_def_id)| {
1133             if let Some(def_id) = opt_def_id {
1134                 if def_id.is_local() {
1135                     return Some((def_id.index, i));
1136                 }
1137             }
1138             None
1139         })),
1140          self.lazy_seq_ref(&tcx.lang_items.missing))
1141     }
1142
1143     fn encode_native_libraries(&mut self) -> LazySeq<NativeLibrary> {
1144         let used_libraries = self.tcx.sess.cstore.used_libraries();
1145         self.lazy_seq(used_libraries)
1146     }
1147
1148     fn encode_codemap(&mut self) -> LazySeq<syntax_pos::FileMap> {
1149         let codemap = self.tcx.sess.codemap();
1150         let all_filemaps = codemap.files.borrow();
1151         self.lazy_seq_ref(all_filemaps.iter()
1152             .filter(|filemap| {
1153                 // No need to export empty filemaps, as they can't contain spans
1154                 // that need translation.
1155                 // Also no need to re-export imported filemaps, as any downstream
1156                 // crate will import them from their original source.
1157                 !filemap.lines.borrow().is_empty() && !filemap.is_imported()
1158             })
1159             .map(|filemap| &**filemap))
1160     }
1161 }
1162
1163 struct ImplVisitor<'a, 'tcx: 'a> {
1164     tcx: TyCtxt<'a, 'tcx, 'tcx>,
1165     impls: FxHashMap<DefId, Vec<DefIndex>>,
1166 }
1167
1168 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ImplVisitor<'a, 'tcx> {
1169     fn visit_item(&mut self, item: &hir::Item) {
1170         if let hir::ItemImpl(..) = item.node {
1171             let impl_id = self.tcx.map.local_def_id(item.id);
1172             if let Some(trait_ref) = self.tcx.impl_trait_ref(impl_id) {
1173                 self.impls
1174                     .entry(trait_ref.def_id)
1175                     .or_insert(vec![])
1176                     .push(impl_id.index);
1177             }
1178         }
1179     }
1180
1181     fn visit_impl_item(&mut self, _impl_item: &'v hir::ImplItem) {
1182         // handled in `visit_item` above
1183     }
1184 }
1185
1186 impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
1187     /// Encodes an index, mapping each trait to its (local) implementations.
1188     fn encode_impls(&mut self) -> LazySeq<TraitImpls> {
1189         let mut visitor = ImplVisitor {
1190             tcx: self.tcx,
1191             impls: FxHashMap(),
1192         };
1193         self.tcx.map.krate().visit_all_item_likes(&mut visitor);
1194
1195         let all_impls: Vec<_> = visitor.impls
1196             .into_iter()
1197             .map(|(trait_def_id, impls)| {
1198                 TraitImpls {
1199                     trait_id: (trait_def_id.krate.as_u32(), trait_def_id.index),
1200                     impls: self.lazy_seq(impls),
1201                 }
1202             })
1203             .collect();
1204
1205         self.lazy_seq(all_impls)
1206     }
1207
1208     // Encodes all reachable symbols in this crate into the metadata.
1209     //
1210     // This pass is seeded off the reachability list calculated in the
1211     // middle::reachable module but filters out items that either don't have a
1212     // symbol associated with them (they weren't translated) or if they're an FFI
1213     // definition (as that's not defined in this crate).
1214     fn encode_reachable(&mut self) -> LazySeq<DefIndex> {
1215         let reachable = self.reachable;
1216         let tcx = self.tcx;
1217         self.lazy_seq(reachable.iter().map(|&id| tcx.map.local_def_id(id).index))
1218     }
1219
1220     fn encode_dylib_dependency_formats(&mut self) -> LazySeq<Option<LinkagePreference>> {
1221         match self.tcx.sess.dependency_formats.borrow().get(&config::CrateTypeDylib) {
1222             Some(arr) => {
1223                 self.lazy_seq(arr.iter().map(|slot| {
1224                     match *slot {
1225                         Linkage::NotLinked |
1226                         Linkage::IncludedFromDylib => None,
1227
1228                         Linkage::Dynamic => Some(LinkagePreference::RequireDynamic),
1229                         Linkage::Static => Some(LinkagePreference::RequireStatic),
1230                     }
1231                 }))
1232             }
1233             None => LazySeq::empty(),
1234         }
1235     }
1236
1237     fn encode_crate_root(&mut self) -> Lazy<CrateRoot> {
1238         let mut i = self.position();
1239         let crate_deps = self.encode_crate_deps();
1240         let dylib_dependency_formats = self.encode_dylib_dependency_formats();
1241         let dep_bytes = self.position() - i;
1242
1243         // Encode the language items.
1244         i = self.position();
1245         let (lang_items, lang_items_missing) = self.encode_lang_items();
1246         let lang_item_bytes = self.position() - i;
1247
1248         // Encode the native libraries used
1249         i = self.position();
1250         let native_libraries = self.encode_native_libraries();
1251         let native_lib_bytes = self.position() - i;
1252
1253         // Encode codemap
1254         i = self.position();
1255         let codemap = self.encode_codemap();
1256         let codemap_bytes = self.position() - i;
1257
1258         // Encode the def IDs of impls, for coherence checking.
1259         i = self.position();
1260         let impls = self.encode_impls();
1261         let impl_bytes = self.position() - i;
1262
1263         // Encode reachability info.
1264         i = self.position();
1265         let reachable_ids = self.encode_reachable();
1266         let reachable_bytes = self.position() - i;
1267
1268         // Encode and index the items.
1269         i = self.position();
1270         let items = self.encode_info_for_items();
1271         let item_bytes = self.position() - i;
1272
1273         i = self.position();
1274         let index = items.write_index(&mut self.opaque.cursor);
1275         let index_bytes = self.position() - i;
1276
1277         let tcx = self.tcx;
1278         let link_meta = self.link_meta;
1279         let is_proc_macro = tcx.sess.crate_types.borrow().contains(&CrateTypeProcMacro);
1280         let root = self.lazy(&CrateRoot {
1281             name: link_meta.crate_name,
1282             triple: tcx.sess.opts.target_triple.clone(),
1283             hash: link_meta.crate_hash,
1284             disambiguator: tcx.sess.local_crate_disambiguator(),
1285             panic_strategy: tcx.sess.panic_strategy(),
1286             plugin_registrar_fn: tcx.sess
1287                 .plugin_registrar_fn
1288                 .get()
1289                 .map(|id| tcx.map.local_def_id(id).index),
1290             macro_derive_registrar: if is_proc_macro {
1291                 let id = tcx.sess.derive_registrar_fn.get().unwrap();
1292                 Some(tcx.map.local_def_id(id).index)
1293             } else {
1294                 None
1295             },
1296
1297             crate_deps: crate_deps,
1298             dylib_dependency_formats: dylib_dependency_formats,
1299             lang_items: lang_items,
1300             lang_items_missing: lang_items_missing,
1301             native_libraries: native_libraries,
1302             codemap: codemap,
1303             impls: impls,
1304             reachable_ids: reachable_ids,
1305             index: index,
1306         });
1307
1308         let total_bytes = self.position();
1309
1310         if self.tcx.sess.meta_stats() {
1311             let mut zero_bytes = 0;
1312             for e in self.opaque.cursor.get_ref() {
1313                 if *e == 0 {
1314                     zero_bytes += 1;
1315                 }
1316             }
1317
1318             println!("metadata stats:");
1319             println!("             dep bytes: {}", dep_bytes);
1320             println!("       lang item bytes: {}", lang_item_bytes);
1321             println!("          native bytes: {}", native_lib_bytes);
1322             println!("         codemap bytes: {}", codemap_bytes);
1323             println!("            impl bytes: {}", impl_bytes);
1324             println!("       reachable bytes: {}", reachable_bytes);
1325             println!("            item bytes: {}", item_bytes);
1326             println!("           index bytes: {}", index_bytes);
1327             println!("            zero bytes: {}", zero_bytes);
1328             println!("           total bytes: {}", total_bytes);
1329         }
1330
1331         root
1332     }
1333 }
1334
1335 // NOTE(eddyb) The following comment was preserved for posterity, even
1336 // though it's no longer relevant as EBML (which uses nested & tagged
1337 // "documents") was replaced with a scheme that can't go out of bounds.
1338 //
1339 // And here we run into yet another obscure archive bug: in which metadata
1340 // loaded from archives may have trailing garbage bytes. Awhile back one of
1341 // our tests was failing sporadically on the OSX 64-bit builders (both nopt
1342 // and opt) by having ebml generate an out-of-bounds panic when looking at
1343 // metadata.
1344 //
1345 // Upon investigation it turned out that the metadata file inside of an rlib
1346 // (and ar archive) was being corrupted. Some compilations would generate a
1347 // metadata file which would end in a few extra bytes, while other
1348 // compilations would not have these extra bytes appended to the end. These
1349 // extra bytes were interpreted by ebml as an extra tag, so they ended up
1350 // being interpreted causing the out-of-bounds.
1351 //
1352 // The root cause of why these extra bytes were appearing was never
1353 // discovered, and in the meantime the solution we're employing is to insert
1354 // the length of the metadata to the start of the metadata. Later on this
1355 // will allow us to slice the metadata to the precise length that we just
1356 // generated regardless of trailing bytes that end up in it.
1357
1358 pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1359                                  cstore: &cstore::CStore,
1360                                  reexports: &def::ExportMap,
1361                                  link_meta: &LinkMeta,
1362                                  reachable: &NodeSet)
1363                                  -> Vec<u8> {
1364     let mut cursor = Cursor::new(vec![]);
1365     cursor.write_all(METADATA_HEADER).unwrap();
1366
1367     // Will be filed with the root position after encoding everything.
1368     cursor.write_all(&[0, 0, 0, 0]).unwrap();
1369
1370     let root = {
1371         let mut ecx = EncodeContext {
1372             opaque: opaque::Encoder::new(&mut cursor),
1373             tcx: tcx,
1374             reexports: reexports,
1375             link_meta: link_meta,
1376             cstore: cstore,
1377             reachable: reachable,
1378             lazy_state: LazyState::NoNode,
1379             type_shorthands: Default::default(),
1380             predicate_shorthands: Default::default(),
1381         };
1382
1383         // Encode the rustc version string in a predictable location.
1384         rustc_version().encode(&mut ecx).unwrap();
1385
1386         // Encode all the entries and extra information in the crate,
1387         // culminating in the `CrateRoot` which points to all of it.
1388         ecx.encode_crate_root()
1389     };
1390     let mut result = cursor.into_inner();
1391
1392     // Encode the root position.
1393     let header = METADATA_HEADER.len();
1394     let pos = root.position;
1395     result[header + 0] = (pos >> 24) as u8;
1396     result[header + 1] = (pos >> 16) as u8;
1397     result[header + 2] = (pos >> 8) as u8;
1398     result[header + 3] = (pos >> 0) as u8;
1399
1400     result
1401 }