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 // Metadata encoding
  12
  13 #![allow(unused_must_use)] // everything is just a MemWriter, can't fail
  14 #![allow(non_camel_case_types)]
  15
  16 use astencode::encode_inlined_item;
  17 use common::*;
  18 use cstore;
  19 use decoder;
  20 use tyencode;
  21 use index::{self, IndexData};
  22
  23 use middle::cstore::{LOCAL_CRATE, CrateStore, InlinedItemRef, LinkMeta, tls};
  24 use middle::def;
  25 use middle::def_id::{CRATE_DEF_INDEX, DefId};
  26 use middle::dependency_format::Linkage;
  27 use middle::stability;
  28 use middle::subst;
  29 use middle::traits::specialization_graph;
  30 use middle::ty::{self, Ty, TyCtxt};
  31 use middle::ty::util::IntTypeExt;
  32
  33 use rustc::back::svh::Svh;
  34 use rustc::front::map::{LinkedPath, PathElem, PathElems};
  35 use rustc::front::map as ast_map;
  36 use rustc::mir::mir_map::MirMap;
  37 use rustc::session::config;
  38 use rustc::util::nodemap::{FnvHashMap, NodeMap, NodeSet};
  39
  40 use serialize::Encodable;
  41 use std::cell::RefCell;
  42 use std::io::prelude::*;
  43 use std::io::{Cursor, SeekFrom};
  44 use std::rc::Rc;
  45 use std::u32;
  46 use syntax::abi::Abi;
  47 use syntax::ast::{self, NodeId, Name, CRATE_NODE_ID, CrateNum};
  48 use syntax::codemap::BytePos;
  49 use syntax::attr;
  50 use syntax::attr::AttrMetaMethods;
  51 use syntax::errors::Handler;
  52 use syntax;
  53 use rbml::writer::Encoder;
  54
  55 use rustc_front::hir::{self, PatKind};
  56 use rustc_front::intravisit::Visitor;
  57 use rustc_front::intravisit;
  58
  59 pub struct EncodeContext<'a, 'tcx: 'a> {
  60     pub diag: &'a Handler,
  61     pub tcx: &'a TyCtxt<'tcx>,
  62     pub reexports: &'a def::ExportMap,
  63     pub item_symbols: &'a RefCell<NodeMap<String>>,
  64     pub link_meta: &'a LinkMeta,
  65     pub cstore: &'a cstore::CStore,
  66     pub type_abbrevs: tyencode::abbrev_map<'tcx>,
  67     pub reachable: &'a NodeSet,
  68     pub mir_map: &'a MirMap<'tcx>,
  69 }
  70
  71 impl<'a, 'tcx> EncodeContext<'a,'tcx> {
  72     fn local_id(&self, def_id: DefId) -> NodeId {
  73         self.tcx.map.as_local_node_id(def_id).unwrap()
  74     }
  75 }
  76
  77 /// "interned" entries referenced by id
  78 #[derive(PartialEq, Eq, Hash)]
  79 pub enum XRef<'tcx> { Predicate(ty::Predicate<'tcx>) }
  80
  81 struct CrateIndex<'tcx> {
  82     items: IndexData,
  83     xrefs: FnvHashMap<XRef<'tcx>, u32>, // sequentially-assigned
  84 }
  85
  86 impl<'tcx> CrateIndex<'tcx> {
  87     fn record(&mut self, id: DefId, rbml_w: &mut Encoder) {
  88         let position = rbml_w.mark_stable_position();
  89         self.items.record(id, position);
  90     }
  91
  92     fn add_xref(&mut self, xref: XRef<'tcx>) -> u32 {
  93         let old_len = self.xrefs.len() as u32;
  94         *self.xrefs.entry(xref).or_insert(old_len)
  95     }
  96 }
  97
  98 fn encode_name(rbml_w: &mut Encoder, name: Name) {
  99     rbml_w.wr_tagged_str(tag_paths_data_name, &name.as_str());
 100 }
 101
 102 fn encode_def_id(rbml_w: &mut Encoder, id: DefId) {
 103     rbml_w.wr_tagged_u64(tag_def_id, def_to_u64(id));
 104 }
 105
 106 /// For every DefId that we create a metadata item for, we include a
 107 /// serialized copy of its DefKey, which allows us to recreate a path.
 108 fn encode_def_id_and_key(ecx: &EncodeContext,
 109                          rbml_w: &mut Encoder,
 110                          def_id: DefId)
 111 {
 112     encode_def_id(rbml_w, def_id);
 113     encode_def_key(ecx, rbml_w, def_id);
 114 }
 115
 116 fn encode_def_key(ecx: &EncodeContext,
 117                   rbml_w: &mut Encoder,
 118                   def_id: DefId)
 119 {
 120     rbml_w.start_tag(tag_def_key);
 121     let def_key = ecx.tcx.map.def_key(def_id);
 122     def_key.encode(rbml_w);
 123     rbml_w.end_tag();
 124 }
 125
 126 fn encode_trait_ref<'a, 'tcx>(rbml_w: &mut Encoder,
 127                               ecx: &EncodeContext<'a, 'tcx>,
 128                               trait_ref: ty::TraitRef<'tcx>,
 129                               tag: usize) {
 130     rbml_w.start_tag(tag);
 131     tyencode::enc_trait_ref(rbml_w.writer, &ecx.ty_str_ctxt(), trait_ref);
 132     rbml_w.mark_stable_position();
 133     rbml_w.end_tag();
 134 }
 135
 136 // Item info table encoding
 137 fn encode_family(rbml_w: &mut Encoder, c: char) {
 138     rbml_w.wr_tagged_u8(tag_items_data_item_family, c as u8);
 139 }
 140
 141 pub fn def_to_u64(did: DefId) -> u64 {
 142     assert!(did.index.as_u32() < u32::MAX);
 143     (did.krate as u64) << 32 | (did.index.as_usize() as u64)
 144 }
 145
 146 pub fn def_to_string(_tcx: &TyCtxt, did: DefId) -> String {
 147     format!("{}:{}", did.krate, did.index.as_usize())
 148 }
 149
 150 fn encode_item_variances(rbml_w: &mut Encoder,
 151                          ecx: &EncodeContext,
 152                          id: NodeId) {
 153     let v = ecx.tcx.item_variances(ecx.tcx.map.local_def_id(id));
 154     rbml_w.start_tag(tag_item_variances);
 155     v.encode(rbml_w);
 156     rbml_w.end_tag();
 157 }
 158
 159 fn encode_bounds_and_type_for_item<'a, 'tcx>(rbml_w: &mut Encoder,
 160                                              ecx: &EncodeContext<'a, 'tcx>,
 161                                              index: &mut CrateIndex<'tcx>,
 162                                              id: NodeId) {
 163     encode_bounds_and_type(rbml_w,
 164                            ecx,
 165                            index,
 166                            &ecx.tcx.lookup_item_type(ecx.tcx.map.local_def_id(id)),
 167                            &ecx.tcx.lookup_predicates(ecx.tcx.map.local_def_id(id)));
 168 }
 169
 170 fn encode_bounds_and_type<'a, 'tcx>(rbml_w: &mut Encoder,
 171                                     ecx: &EncodeContext<'a, 'tcx>,
 172                                     index: &mut CrateIndex<'tcx>,
 173                                     scheme: &ty::TypeScheme<'tcx>,
 174                                     predicates: &ty::GenericPredicates<'tcx>) {
 175     encode_generics(rbml_w, ecx, index,
 176                     &scheme.generics, &predicates, tag_item_generics);
 177     encode_type(ecx, rbml_w, scheme.ty);
 178 }
 179
 180 fn encode_variant_id(rbml_w: &mut Encoder, vid: DefId) {
 181     let id = def_to_u64(vid);
 182     rbml_w.wr_tagged_u64(tag_items_data_item_variant, id);
 183     rbml_w.wr_tagged_u64(tag_mod_child, id);
 184 }
 185
 186 fn write_closure_type<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 187                             rbml_w: &mut Encoder,
 188                             closure_type: &ty::ClosureTy<'tcx>) {
 189     tyencode::enc_closure_ty(rbml_w.writer, &ecx.ty_str_ctxt(), closure_type);
 190     rbml_w.mark_stable_position();
 191 }
 192
 193 fn encode_type<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 194                          rbml_w: &mut Encoder,
 195                          typ: Ty<'tcx>) {
 196     rbml_w.start_tag(tag_items_data_item_type);
 197     tyencode::enc_ty(rbml_w.writer, &ecx.ty_str_ctxt(), typ);
 198     rbml_w.mark_stable_position();
 199     rbml_w.end_tag();
 200 }
 201
 202 fn encode_region(ecx: &EncodeContext,
 203                  rbml_w: &mut Encoder,
 204                  r: ty::Region) {
 205     rbml_w.start_tag(tag_items_data_region);
 206     tyencode::enc_region(rbml_w.writer, &ecx.ty_str_ctxt(), r);
 207     rbml_w.mark_stable_position();
 208     rbml_w.end_tag();
 209 }
 210
 211 fn encode_symbol(ecx: &EncodeContext,
 212                  rbml_w: &mut Encoder,
 213                  id: NodeId) {
 214     match ecx.item_symbols.borrow().get(&id) {
 215         Some(x) => {
 216             debug!("encode_symbol(id={}, str={})", id, *x);
 217             rbml_w.wr_tagged_str(tag_items_data_item_symbol, x);
 218         }
 219         None => {
 220             ecx.diag.bug(&format!("encode_symbol: id not found {}", id));
 221         }
 222     }
 223 }
 224
 225 fn encode_disr_val(_: &EncodeContext,
 226                    rbml_w: &mut Encoder,
 227                    disr_val: ty::Disr) {
 228     // convert to u64 so just the number is printed, without any type info
 229     rbml_w.wr_tagged_str(tag_disr_val, &disr_val.to_u64_unchecked().to_string());
 230 }
 231
 232 fn encode_parent_item(rbml_w: &mut Encoder, id: DefId) {
 233     rbml_w.wr_tagged_u64(tag_items_data_parent_item, def_to_u64(id));
 234 }
 235
 236 fn encode_struct_fields(rbml_w: &mut Encoder,
 237                         variant: ty::VariantDef) {
 238     for f in &variant.fields {
 239         if variant.is_tuple_struct() {
 240             rbml_w.start_tag(tag_item_unnamed_field);
 241         } else {
 242             rbml_w.start_tag(tag_item_field);
 243             encode_name(rbml_w, f.name);
 244         }
 245         encode_struct_field_family(rbml_w, f.vis);
 246         encode_def_id(rbml_w, f.did);
 247         rbml_w.end_tag();
 248     }
 249 }
 250
 251 fn encode_enum_variant_info<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 252                                       rbml_w: &mut Encoder,
 253                                       did: DefId,
 254                                       vis: hir::Visibility,
 255                                       index: &mut CrateIndex<'tcx>) {
 256     debug!("encode_enum_variant_info(did={:?})", did);
 257     let repr_hints = ecx.tcx.lookup_repr_hints(did);
 258     let repr_type = ecx.tcx.enum_repr_type(repr_hints.get(0));
 259     let mut disr_val = repr_type.initial_discriminant(&ecx.tcx);
 260     let def = ecx.tcx.lookup_adt_def(did);
 261     for variant in &def.variants {
 262         let vid = variant.did;
 263         let variant_node_id = ecx.local_id(vid);
 264
 265         if let ty::VariantKind::Struct = variant.kind() {
 266             // tuple-like enum variant fields aren't really items so
 267             // don't try to encode them.
 268             for field in &variant.fields {
 269                 encode_field(ecx, rbml_w, field, index);
 270             }
 271         }
 272
 273         index.record(vid, rbml_w);
 274         rbml_w.start_tag(tag_items_data_item);
 275         encode_def_id_and_key(ecx, rbml_w, vid);
 276         encode_family(rbml_w, match variant.kind() {
 277             ty::VariantKind::Struct => 'V',
 278             ty::VariantKind::Tuple => 'v',
 279             ty::VariantKind::Unit => 'w',
 280         });
 281         encode_name(rbml_w, variant.name);
 282         encode_parent_item(rbml_w, did);
 283         encode_visibility(rbml_w, vis);
 284
 285         let attrs = ecx.tcx.get_attrs(vid);
 286         encode_attributes(rbml_w, &attrs);
 287         encode_repr_attrs(rbml_w, ecx, &attrs);
 288
 289         let stab = stability::lookup_stability(ecx.tcx, vid);
 290         let depr = stability::lookup_deprecation(ecx.tcx, vid);
 291         encode_stability(rbml_w, stab);
 292         encode_deprecation(rbml_w, depr);
 293
 294         encode_struct_fields(rbml_w, variant);
 295
 296         let specified_disr_val = variant.disr_val;
 297         if specified_disr_val != disr_val {
 298             encode_disr_val(ecx, rbml_w, specified_disr_val);
 299             disr_val = specified_disr_val;
 300         }
 301         encode_bounds_and_type_for_item(rbml_w, ecx, index, variant_node_id);
 302
 303         ecx.tcx.map.with_path(variant_node_id, |path| encode_path(rbml_w, path));
 304         rbml_w.end_tag();
 305         disr_val = disr_val.wrap_incr();
 306     }
 307 }
 308
 309 fn encode_path<PI: Iterator<Item=PathElem>>(rbml_w: &mut Encoder, path: PI) {
 310     let path = path.collect::<Vec<_>>();
 311     rbml_w.start_tag(tag_path);
 312     rbml_w.wr_tagged_u32(tag_path_len, path.len() as u32);
 313     for pe in &path {
 314         let tag = match *pe {
 315             ast_map::PathMod(_) => tag_path_elem_mod,
 316             ast_map::PathName(_) => tag_path_elem_name
 317         };
 318         rbml_w.wr_tagged_str(tag, &pe.name().as_str());
 319     }
 320     rbml_w.end_tag();
 321 }
 322
 323 /// Iterates through "auxiliary node IDs", which are node IDs that describe
 324 /// top-level items that are sub-items of the given item. Specifically:
 325 ///
 326 /// * For newtype structs, iterates through the node ID of the constructor.
 327 fn each_auxiliary_node_id<F>(item: &hir::Item, callback: F) -> bool where
 328     F: FnOnce(NodeId) -> bool,
 329 {
 330     let mut continue_ = true;
 331     match item.node {
 332         hir::ItemStruct(ref struct_def, _) => {
 333             // If this is a newtype struct, return the constructor.
 334             if struct_def.is_tuple() {
 335                 continue_ = callback(struct_def.id());
 336             }
 337         }
 338         _ => {}
 339     }
 340
 341     continue_
 342 }
 343
 344 fn encode_reexports(ecx: &EncodeContext,
 345                     rbml_w: &mut Encoder,
 346                     id: NodeId) {
 347     debug!("(encoding info for module) encoding reexports for {}", id);
 348     match ecx.reexports.get(&id) {
 349         Some(exports) => {
 350             debug!("(encoding info for module) found reexports for {}", id);
 351             for exp in exports {
 352                 debug!("(encoding info for module) reexport '{}' ({:?}) for \
 353                         {}",
 354                        exp.name,
 355                        exp.def_id,
 356                        id);
 357                 rbml_w.start_tag(tag_items_data_item_reexport);
 358                 rbml_w.wr_tagged_u64(tag_items_data_item_reexport_def_id,
 359                                      def_to_u64(exp.def_id));
 360                 rbml_w.wr_tagged_str(tag_items_data_item_reexport_name,
 361                                      &exp.name.as_str());
 362                 rbml_w.end_tag();
 363             }
 364         },
 365         None => debug!("(encoding info for module) found no reexports for {}", id),
 366     }
 367 }
 368
 369 fn encode_info_for_mod(ecx: &EncodeContext,
 370                        rbml_w: &mut Encoder,
 371                        md: &hir::Mod,
 372                        attrs: &[ast::Attribute],
 373                        id: NodeId,
 374                        path: PathElems,
 375                        name: Name,
 376                        vis: hir::Visibility) {
 377     rbml_w.start_tag(tag_items_data_item);
 378     encode_def_id_and_key(ecx, rbml_w, ecx.tcx.map.local_def_id(id));
 379     encode_family(rbml_w, 'm');
 380     encode_name(rbml_w, name);
 381     debug!("(encoding info for module) encoding info for module ID {}", id);
 382
 383     // Encode info about all the module children.
 384     for item_id in &md.item_ids {
 385         rbml_w.wr_tagged_u64(tag_mod_child,
 386                              def_to_u64(ecx.tcx.map.local_def_id(item_id.id)));
 387
 388         let item = ecx.tcx.map.expect_item(item_id.id);
 389         each_auxiliary_node_id(item, |auxiliary_node_id| {
 390             rbml_w.wr_tagged_u64(tag_mod_child,
 391                                  def_to_u64(ecx.tcx.map.local_def_id(auxiliary_node_id)));
 392             true
 393         });
 394     }
 395
 396     encode_path(rbml_w, path.clone());
 397     encode_visibility(rbml_w, vis);
 398
 399     let stab = stability::lookup_stability(ecx.tcx, ecx.tcx.map.local_def_id(id));
 400     let depr = stability::lookup_deprecation(ecx.tcx, ecx.tcx.map.local_def_id(id));
 401     encode_stability(rbml_w, stab);
 402     encode_deprecation(rbml_w, depr);
 403
 404     // Encode the reexports of this module, if this module is public.
 405     if vis == hir::Public {
 406         debug!("(encoding info for module) encoding reexports for {}", id);
 407         encode_reexports(ecx, rbml_w, id);
 408     }
 409     encode_attributes(rbml_w, attrs);
 410
 411     rbml_w.end_tag();
 412 }
 413
 414 fn encode_struct_field_family(rbml_w: &mut Encoder,
 415                               visibility: hir::Visibility) {
 416     encode_family(rbml_w, match visibility {
 417         hir::Public => 'g',
 418         hir::Inherited => 'N'
 419     });
 420 }
 421
 422 fn encode_visibility(rbml_w: &mut Encoder, visibility: hir::Visibility) {
 423     let ch = match visibility {
 424         hir::Public => 'y',
 425         hir::Inherited => 'i',
 426     };
 427     rbml_w.wr_tagged_u8(tag_items_data_item_visibility, ch as u8);
 428 }
 429
 430 fn encode_constness(rbml_w: &mut Encoder, constness: hir::Constness) {
 431     rbml_w.start_tag(tag_items_data_item_constness);
 432     let ch = match constness {
 433         hir::Constness::Const => 'c',
 434         hir::Constness::NotConst => 'n',
 435     };
 436     rbml_w.wr_str(&ch.to_string());
 437     rbml_w.end_tag();
 438 }
 439
 440 fn encode_defaultness(rbml_w: &mut Encoder, defaultness: hir::Defaultness) {
 441     let ch = match defaultness {
 442         hir::Defaultness::Default => 'd',
 443         hir::Defaultness::Final => 'f',
 444     };
 445     rbml_w.wr_tagged_u8(tag_items_data_item_defaultness, ch as u8);
 446 }
 447
 448 fn encode_explicit_self(rbml_w: &mut Encoder,
 449                         explicit_self: &ty::ExplicitSelfCategory) {
 450     let tag = tag_item_trait_method_explicit_self;
 451
 452     // Encode the base self type.
 453     match *explicit_self {
 454         ty::ExplicitSelfCategory::Static => {
 455             rbml_w.wr_tagged_bytes(tag, &['s' as u8]);
 456         }
 457         ty::ExplicitSelfCategory::ByValue => {
 458             rbml_w.wr_tagged_bytes(tag, &['v' as u8]);
 459         }
 460         ty::ExplicitSelfCategory::ByBox => {
 461             rbml_w.wr_tagged_bytes(tag, &['~' as u8]);
 462         }
 463         ty::ExplicitSelfCategory::ByReference(_, m) => {
 464             // FIXME(#4846) encode custom lifetime
 465             let ch = encode_mutability(m);
 466             rbml_w.wr_tagged_bytes(tag, &['&' as u8, ch]);
 467         }
 468     }
 469
 470     fn encode_mutability(m: hir::Mutability) -> u8 {
 471         match m {
 472             hir::MutImmutable => 'i' as u8,
 473             hir::MutMutable => 'm' as u8,
 474         }
 475     }
 476 }
 477
 478 fn encode_item_sort(rbml_w: &mut Encoder, sort: char) {
 479     rbml_w.wr_tagged_u8(tag_item_trait_item_sort, sort as u8);
 480 }
 481
 482 fn encode_field<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 483                           rbml_w: &mut Encoder,
 484                           field: ty::FieldDef<'tcx>,
 485                           index: &mut CrateIndex<'tcx>) {
 486     let nm = field.name;
 487     let id = ecx.local_id(field.did);
 488
 489     index.record(field.did, rbml_w);
 490     rbml_w.start_tag(tag_items_data_item);
 491     debug!("encode_field: encoding {} {}", nm, id);
 492     encode_struct_field_family(rbml_w, field.vis);
 493     encode_name(rbml_w, nm);
 494     encode_bounds_and_type_for_item(rbml_w, ecx, index, id);
 495     encode_def_id_and_key(ecx, rbml_w, field.did);
 496
 497     let stab = stability::lookup_stability(ecx.tcx, field.did);
 498     let depr = stability::lookup_deprecation(ecx.tcx, field.did);
 499     encode_stability(rbml_w, stab);
 500     encode_deprecation(rbml_w, depr);
 501
 502     rbml_w.end_tag();
 503 }
 504
 505 fn encode_info_for_struct_ctor<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 506                                          rbml_w: &mut Encoder,
 507                                          name: Name,
 508                                          struct_def: &hir::VariantData,
 509                                          index: &mut CrateIndex<'tcx>,
 510                                          struct_id: NodeId) {
 511     let ctor_id = struct_def.id();
 512     let ctor_def_id = ecx.tcx.map.local_def_id(ctor_id);
 513
 514     index.record(ctor_def_id, rbml_w);
 515     rbml_w.start_tag(tag_items_data_item);
 516     encode_def_id_and_key(ecx, rbml_w, ctor_def_id);
 517     encode_family(rbml_w, match *struct_def {
 518         hir::VariantData::Struct(..) => 'S',
 519         hir::VariantData::Tuple(..) => 's',
 520         hir::VariantData::Unit(..) => 'u',
 521     });
 522     encode_bounds_and_type_for_item(rbml_w, ecx, index, ctor_id);
 523     encode_name(rbml_w, name);
 524     ecx.tcx.map.with_path(ctor_id, |path| encode_path(rbml_w, path));
 525     encode_parent_item(rbml_w, ecx.tcx.map.local_def_id(struct_id));
 526
 527     if ecx.item_symbols.borrow().contains_key(&ctor_id) {
 528         encode_symbol(ecx, rbml_w, ctor_id);
 529     }
 530
 531     let stab = stability::lookup_stability(ecx.tcx, ecx.tcx.map.local_def_id(ctor_id));
 532     let depr= stability::lookup_deprecation(ecx.tcx, ecx.tcx.map.local_def_id(ctor_id));
 533     encode_stability(rbml_w, stab);
 534     encode_deprecation(rbml_w, depr);
 535
 536     // indicate that this is a tuple struct ctor, because downstream users will normally want
 537     // the tuple struct definition, but without this there is no way for them to tell that
 538     // they actually have a ctor rather than a normal function
 539     rbml_w.wr_tagged_bytes(tag_items_data_item_is_tuple_struct_ctor, &[]);
 540
 541     rbml_w.end_tag();
 542 }
 543
 544 fn encode_generics<'a, 'tcx>(rbml_w: &mut Encoder,
 545                              ecx: &EncodeContext<'a, 'tcx>,
 546                              index: &mut CrateIndex<'tcx>,
 547                              generics: &ty::Generics<'tcx>,
 548                              predicates: &ty::GenericPredicates<'tcx>,
 549                              tag: usize)
 550 {
 551     rbml_w.start_tag(tag);
 552
 553     for param in &generics.types {
 554         rbml_w.start_tag(tag_type_param_def);
 555         tyencode::enc_type_param_def(rbml_w.writer, &ecx.ty_str_ctxt(), param);
 556         rbml_w.mark_stable_position();
 557         rbml_w.end_tag();
 558     }
 559
 560     // Region parameters
 561     for param in &generics.regions {
 562         rbml_w.start_tag(tag_region_param_def);
 563
 564         rbml_w.start_tag(tag_region_param_def_ident);
 565         encode_name(rbml_w, param.name);
 566         rbml_w.end_tag();
 567
 568         rbml_w.wr_tagged_u64(tag_region_param_def_def_id,
 569                              def_to_u64(param.def_id));
 570
 571         rbml_w.wr_tagged_u64(tag_region_param_def_space,
 572                              param.space.to_uint() as u64);
 573
 574         rbml_w.wr_tagged_u64(tag_region_param_def_index,
 575                              param.index as u64);
 576
 577         for &bound_region in &param.bounds {
 578             encode_region(ecx, rbml_w, bound_region);
 579         }
 580
 581         rbml_w.end_tag();
 582     }
 583
 584     encode_predicates_in_current_doc(rbml_w, ecx, index, predicates);
 585
 586     rbml_w.end_tag();
 587 }
 588
 589 fn encode_predicates_in_current_doc<'a,'tcx>(rbml_w: &mut Encoder,
 590                                              _ecx: &EncodeContext<'a,'tcx>,
 591                                              index: &mut CrateIndex<'tcx>,
 592                                              predicates: &ty::GenericPredicates<'tcx>)
 593 {
 594     for (space, _, predicate) in predicates.predicates.iter_enumerated() {
 595         let tag = match space {
 596             subst::TypeSpace => tag_type_predicate,
 597             subst::SelfSpace => tag_self_predicate,
 598             subst::FnSpace => tag_fn_predicate
 599         };
 600
 601         rbml_w.wr_tagged_u32(tag,
 602             index.add_xref(XRef::Predicate(predicate.clone())));
 603     }
 604 }
 605
 606 fn encode_predicates<'a,'tcx>(rbml_w: &mut Encoder,
 607                               ecx: &EncodeContext<'a,'tcx>,
 608                               index: &mut CrateIndex<'tcx>,
 609                               predicates: &ty::GenericPredicates<'tcx>,
 610                               tag: usize)
 611 {
 612     rbml_w.start_tag(tag);
 613     encode_predicates_in_current_doc(rbml_w, ecx, index, predicates);
 614     rbml_w.end_tag();
 615 }
 616
 617 fn encode_method_ty_fields<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 618                                      rbml_w: &mut Encoder,
 619                                      index: &mut CrateIndex<'tcx>,
 620                                      method_ty: &ty::Method<'tcx>) {
 621     encode_def_id_and_key(ecx, rbml_w, method_ty.def_id);
 622     encode_name(rbml_w, method_ty.name);
 623     encode_generics(rbml_w, ecx, index,
 624                     &method_ty.generics, &method_ty.predicates,
 625                     tag_method_ty_generics);
 626     encode_visibility(rbml_w, method_ty.vis);
 627     encode_explicit_self(rbml_w, &method_ty.explicit_self);
 628     match method_ty.explicit_self {
 629         ty::ExplicitSelfCategory::Static => {
 630             encode_family(rbml_w, STATIC_METHOD_FAMILY);
 631         }
 632         _ => encode_family(rbml_w, METHOD_FAMILY)
 633     }
 634 }
 635
 636 fn encode_info_for_associated_const<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 637                                               rbml_w: &mut Encoder,
 638                                               index: &mut CrateIndex<'tcx>,
 639                                               associated_const: &ty::AssociatedConst,
 640                                               impl_path: PathElems,
 641                                               parent_id: NodeId,
 642                                               impl_item_opt: Option<&hir::ImplItem>) {
 643     debug!("encode_info_for_associated_const({:?},{:?})",
 644            associated_const.def_id,
 645            associated_const.name);
 646
 647     index.record(associated_const.def_id, rbml_w);
 648     rbml_w.start_tag(tag_items_data_item);
 649
 650     encode_def_id_and_key(ecx, rbml_w, associated_const.def_id);
 651     encode_name(rbml_w, associated_const.name);
 652     encode_visibility(rbml_w, associated_const.vis);
 653     encode_family(rbml_w, 'C');
 654
 655     encode_parent_item(rbml_w, ecx.tcx.map.local_def_id(parent_id));
 656     encode_item_sort(rbml_w, 'C');
 657
 658     encode_bounds_and_type_for_item(rbml_w, ecx, index,
 659                                     ecx.local_id(associated_const.def_id));
 660
 661     let stab = stability::lookup_stability(ecx.tcx, associated_const.def_id);
 662     let depr = stability::lookup_deprecation(ecx.tcx, associated_const.def_id);
 663     encode_stability(rbml_w, stab);
 664     encode_deprecation(rbml_w, depr);
 665
 666     let elem = ast_map::PathName(associated_const.name);
 667     encode_path(rbml_w, impl_path.chain(Some(elem)));
 668
 669     if let Some(ii) = impl_item_opt {
 670         encode_attributes(rbml_w, &ii.attrs);
 671         encode_defaultness(rbml_w, ii.defaultness);
 672         encode_inlined_item(ecx,
 673                             rbml_w,
 674                             InlinedItemRef::ImplItem(ecx.tcx.map.local_def_id(parent_id),
 675                                                      ii));
 676         encode_mir(ecx, rbml_w, ii.id);
 677     }
 678
 679     rbml_w.end_tag();
 680 }
 681
 682 fn encode_info_for_method<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 683                                     rbml_w: &mut Encoder,
 684                                     index: &mut CrateIndex<'tcx>,
 685                                     m: &ty::Method<'tcx>,
 686                                     impl_path: PathElems,
 687                                     is_default_impl: bool,
 688                                     parent_id: NodeId,
 689                                     impl_item_opt: Option<&hir::ImplItem>) {
 690
 691     debug!("encode_info_for_method: {:?} {:?}", m.def_id,
 692            m.name);
 693     index.record(m.def_id, rbml_w);
 694     rbml_w.start_tag(tag_items_data_item);
 695
 696     encode_method_ty_fields(ecx, rbml_w, index, m);
 697     encode_parent_item(rbml_w, ecx.tcx.map.local_def_id(parent_id));
 698     encode_item_sort(rbml_w, 'r');
 699
 700     let stab = stability::lookup_stability(ecx.tcx, m.def_id);
 701     let depr = stability::lookup_deprecation(ecx.tcx, m.def_id);
 702     encode_stability(rbml_w, stab);
 703     encode_deprecation(rbml_w, depr);
 704
 705     let m_node_id = ecx.local_id(m.def_id);
 706     encode_bounds_and_type_for_item(rbml_w, ecx, index, m_node_id);
 707
 708     let elem = ast_map::PathName(m.name);
 709     encode_path(rbml_w, impl_path.chain(Some(elem)));
 710     if let Some(impl_item) = impl_item_opt {
 711         if let hir::ImplItemKind::Method(ref sig, _) = impl_item.node {
 712             encode_attributes(rbml_w, &impl_item.attrs);
 713             let scheme = ecx.tcx.lookup_item_type(m.def_id);
 714             let any_types = !scheme.generics.types.is_empty();
 715             let needs_inline = any_types || is_default_impl ||
 716                                attr::requests_inline(&impl_item.attrs);
 717             if needs_inline || sig.constness == hir::Constness::Const {
 718                 encode_inlined_item(ecx,
 719                                     rbml_w,
 720                                     InlinedItemRef::ImplItem(ecx.tcx.map.local_def_id(parent_id),
 721                                                              impl_item));
 722                 encode_mir(ecx, rbml_w, impl_item.id);
 723             }
 724             encode_constness(rbml_w, sig.constness);
 725             encode_defaultness(rbml_w, impl_item.defaultness);
 726             if !any_types {
 727                 let m_id = ecx.local_id(m.def_id);
 728                 encode_symbol(ecx, rbml_w, m_id);
 729             }
 730             encode_method_argument_names(rbml_w, &sig.decl);
 731         }
 732     }
 733
 734     rbml_w.end_tag();
 735 }
 736
 737 fn encode_info_for_associated_type<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 738                                              rbml_w: &mut Encoder,
 739                                              index: &mut CrateIndex<'tcx>,
 740                                              associated_type: &ty::AssociatedType<'tcx>,
 741                                              impl_path: PathElems,
 742                                              parent_id: NodeId,
 743                                              impl_item_opt: Option<&hir::ImplItem>) {
 744     debug!("encode_info_for_associated_type({:?},{:?})",
 745            associated_type.def_id,
 746            associated_type.name);
 747
 748     index.record(associated_type.def_id, rbml_w);
 749     rbml_w.start_tag(tag_items_data_item);
 750
 751     encode_def_id_and_key(ecx, rbml_w, associated_type.def_id);
 752     encode_name(rbml_w, associated_type.name);
 753     encode_visibility(rbml_w, associated_type.vis);
 754     encode_family(rbml_w, 'y');
 755     encode_parent_item(rbml_w, ecx.tcx.map.local_def_id(parent_id));
 756     encode_item_sort(rbml_w, 't');
 757
 758     let stab = stability::lookup_stability(ecx.tcx, associated_type.def_id);
 759     let depr = stability::lookup_deprecation(ecx.tcx, associated_type.def_id);
 760     encode_stability(rbml_w, stab);
 761     encode_deprecation(rbml_w, depr);
 762
 763     let elem = ast_map::PathName(associated_type.name);
 764     encode_path(rbml_w, impl_path.chain(Some(elem)));
 765
 766     if let Some(ii) = impl_item_opt {
 767         encode_attributes(rbml_w, &ii.attrs);
 768         encode_defaultness(rbml_w, ii.defaultness);
 769     } else {
 770         encode_predicates(rbml_w, ecx, index,
 771                           &ecx.tcx.lookup_predicates(associated_type.def_id),
 772                           tag_item_generics);
 773     }
 774
 775     if let Some(ty) = associated_type.ty {
 776         encode_type(ecx, rbml_w, ty);
 777     }
 778
 779     rbml_w.end_tag();
 780 }
 781
 782 fn encode_method_argument_names(rbml_w: &mut Encoder,
 783                                 decl: &hir::FnDecl) {
 784     rbml_w.start_tag(tag_method_argument_names);
 785     for arg in &decl.inputs {
 786         let tag = tag_method_argument_name;
 787         if let PatKind::Ident(_, ref path1, _) = arg.pat.node {
 788             let name = path1.node.name.as_str();
 789             rbml_w.wr_tagged_bytes(tag, name.as_bytes());
 790         } else {
 791             rbml_w.wr_tagged_bytes(tag, &[]);
 792         }
 793     }
 794     rbml_w.end_tag();
 795 }
 796
 797 fn encode_repr_attrs(rbml_w: &mut Encoder,
 798                      ecx: &EncodeContext,
 799                      attrs: &[ast::Attribute]) {
 800     let mut repr_attrs = Vec::new();
 801     for attr in attrs {
 802         repr_attrs.extend(attr::find_repr_attrs(ecx.tcx.sess.diagnostic(),
 803                                                 attr));
 804     }
 805     rbml_w.start_tag(tag_items_data_item_repr);
 806     repr_attrs.encode(rbml_w);
 807     rbml_w.end_tag();
 808 }
 809
 810 fn encode_mir(ecx: &EncodeContext, rbml_w: &mut Encoder, node_id: NodeId) {
 811     if let Some(mir) = ecx.mir_map.map.get(&node_id) {
 812         rbml_w.start_tag(tag_mir as usize);
 813         rbml_w.emit_opaque(|opaque_encoder| {
 814             tls::enter_encoding_context(ecx, opaque_encoder, |_, opaque_encoder| {
 815                 Encodable::encode(mir, opaque_encoder)
 816             })
 817         }).unwrap();
 818         rbml_w.end_tag();
 819     }
 820 }
 821
 822 const FN_FAMILY: char = 'f';
 823 const STATIC_METHOD_FAMILY: char = 'F';
 824 const METHOD_FAMILY: char = 'h';
 825
 826 // Encodes the inherent implementations of a structure, enumeration, or trait.
 827 fn encode_inherent_implementations(ecx: &EncodeContext,
 828                                    rbml_w: &mut Encoder,
 829                                    def_id: DefId) {
 830     match ecx.tcx.inherent_impls.borrow().get(&def_id) {
 831         None => {}
 832         Some(implementations) => {
 833             for &impl_def_id in implementations.iter() {
 834                 rbml_w.start_tag(tag_items_data_item_inherent_impl);
 835                 encode_def_id(rbml_w, impl_def_id);
 836                 rbml_w.end_tag();
 837             }
 838         }
 839     }
 840 }
 841
 842 fn encode_stability(rbml_w: &mut Encoder, stab_opt: Option<&attr::Stability>) {
 843     stab_opt.map(|stab| {
 844         rbml_w.start_tag(tag_items_data_item_stability);
 845         stab.encode(rbml_w).unwrap();
 846         rbml_w.end_tag();
 847     });
 848 }
 849
 850 fn encode_deprecation(rbml_w: &mut Encoder, depr_opt: Option<attr::Deprecation>) {
 851     depr_opt.map(|depr| {
 852         rbml_w.start_tag(tag_items_data_item_deprecation);
 853         depr.encode(rbml_w).unwrap();
 854         rbml_w.end_tag();
 855     });
 856 }
 857
 858 fn encode_parent_impl(rbml_w: &mut Encoder, parent_opt: Option<DefId>) {
 859     parent_opt.map(|parent| {
 860         rbml_w.wr_tagged_u64(tag_items_data_parent_impl, def_to_u64(parent));
 861     });
 862 }
 863
 864 fn encode_xrefs<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 865                           rbml_w: &mut Encoder,
 866                           xrefs: FnvHashMap<XRef<'tcx>, u32>)
 867 {
 868     let mut xref_positions = vec![0; xrefs.len()];
 869     rbml_w.start_tag(tag_xref_data);
 870     for (xref, id) in xrefs.into_iter() {
 871         xref_positions[id as usize] = rbml_w.mark_stable_position() as u32;
 872         match xref {
 873             XRef::Predicate(p) => {
 874                 tyencode::enc_predicate(rbml_w.writer, &ecx.ty_str_ctxt(), &p)
 875             }
 876         }
 877     }
 878     rbml_w.mark_stable_position();
 879     rbml_w.end_tag();
 880
 881     rbml_w.start_tag(tag_xref_index);
 882     index::write_dense_index(xref_positions, rbml_w.writer);
 883     rbml_w.end_tag();
 884 }
 885
 886 fn encode_info_for_item<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
 887                                   rbml_w: &mut Encoder,
 888                                   item: &hir::Item,
 889                                   index: &mut CrateIndex<'tcx>,
 890                                   path: PathElems,
 891                                   vis: hir::Visibility) {
 892     let tcx = ecx.tcx;
 893
 894     debug!("encoding info for item at {}",
 895            tcx.sess.codemap().span_to_string(item.span));
 896
 897     let def_id = ecx.tcx.map.local_def_id(item.id);
 898     let stab = stability::lookup_stability(tcx, ecx.tcx.map.local_def_id(item.id));
 899     let depr = stability::lookup_deprecation(tcx, ecx.tcx.map.local_def_id(item.id));
 900
 901     match item.node {
 902       hir::ItemStatic(_, m, _) => {
 903         index.record(def_id, rbml_w);
 904         rbml_w.start_tag(tag_items_data_item);
 905         encode_def_id_and_key(ecx, rbml_w, def_id);
 906         if m == hir::MutMutable {
 907             encode_family(rbml_w, 'b');
 908         } else {
 909             encode_family(rbml_w, 'c');
 910         }
 911         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
 912         encode_symbol(ecx, rbml_w, item.id);
 913         encode_name(rbml_w, item.name);
 914         encode_path(rbml_w, path);
 915         encode_visibility(rbml_w, vis);
 916         encode_stability(rbml_w, stab);
 917         encode_deprecation(rbml_w, depr);
 918         encode_attributes(rbml_w, &item.attrs);
 919         rbml_w.end_tag();
 920       }
 921       hir::ItemConst(_, _) => {
 922         index.record(def_id, rbml_w);
 923         rbml_w.start_tag(tag_items_data_item);
 924         encode_def_id_and_key(ecx, rbml_w, def_id);
 925         encode_family(rbml_w, 'C');
 926         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
 927         encode_name(rbml_w, item.name);
 928         encode_path(rbml_w, path);
 929         encode_attributes(rbml_w, &item.attrs);
 930         encode_inlined_item(ecx, rbml_w, InlinedItemRef::Item(item));
 931         encode_mir(ecx, rbml_w, item.id);
 932         encode_visibility(rbml_w, vis);
 933         encode_stability(rbml_w, stab);
 934         encode_deprecation(rbml_w, depr);
 935         rbml_w.end_tag();
 936       }
 937       hir::ItemFn(ref decl, _, constness, _, ref generics, _) => {
 938         index.record(def_id, rbml_w);
 939         rbml_w.start_tag(tag_items_data_item);
 940         encode_def_id_and_key(ecx, rbml_w, def_id);
 941         encode_family(rbml_w, FN_FAMILY);
 942         let tps_len = generics.ty_params.len();
 943         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
 944         encode_name(rbml_w, item.name);
 945         encode_path(rbml_w, path);
 946         encode_attributes(rbml_w, &item.attrs);
 947         let needs_inline = tps_len > 0 || attr::requests_inline(&item.attrs);
 948         if needs_inline || constness == hir::Constness::Const {
 949             encode_inlined_item(ecx, rbml_w, InlinedItemRef::Item(item));
 950             encode_mir(ecx, rbml_w, item.id);
 951         }
 952         if tps_len == 0 {
 953             encode_symbol(ecx, rbml_w, item.id);
 954         }
 955         encode_constness(rbml_w, constness);
 956         encode_visibility(rbml_w, vis);
 957         encode_stability(rbml_w, stab);
 958         encode_deprecation(rbml_w, depr);
 959         encode_method_argument_names(rbml_w, &decl);
 960         rbml_w.end_tag();
 961       }
 962       hir::ItemMod(ref m) => {
 963         index.record(def_id, rbml_w);
 964         encode_info_for_mod(ecx,
 965                             rbml_w,
 966                             m,
 967                             &item.attrs,
 968                             item.id,
 969                             path,
 970                             item.name,
 971                             item.vis);
 972       }
 973       hir::ItemForeignMod(ref fm) => {
 974         index.record(def_id, rbml_w);
 975         rbml_w.start_tag(tag_items_data_item);
 976         encode_def_id_and_key(ecx, rbml_w, def_id);
 977         encode_family(rbml_w, 'n');
 978         encode_name(rbml_w, item.name);
 979         encode_path(rbml_w, path);
 980
 981         // Encode all the items in this module.
 982         for foreign_item in &fm.items {
 983             rbml_w.wr_tagged_u64(tag_mod_child,
 984                                  def_to_u64(ecx.tcx.map.local_def_id(foreign_item.id)));
 985         }
 986         encode_visibility(rbml_w, vis);
 987         encode_stability(rbml_w, stab);
 988         encode_deprecation(rbml_w, depr);
 989         rbml_w.end_tag();
 990       }
 991       hir::ItemTy(..) => {
 992         index.record(def_id, rbml_w);
 993         rbml_w.start_tag(tag_items_data_item);
 994         encode_def_id_and_key(ecx, rbml_w, def_id);
 995         encode_family(rbml_w, 'y');
 996         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
 997         encode_name(rbml_w, item.name);
 998         encode_path(rbml_w, path);
 999         encode_visibility(rbml_w, vis);
1000         encode_stability(rbml_w, stab);
1001         encode_deprecation(rbml_w, depr);
1002         rbml_w.end_tag();
1003       }
1004       hir::ItemEnum(ref enum_definition, _) => {
1005         index.record(def_id, rbml_w);
1006
1007         rbml_w.start_tag(tag_items_data_item);
1008         encode_def_id_and_key(ecx, rbml_w, def_id);
1009         encode_family(rbml_w, 't');
1010         encode_item_variances(rbml_w, ecx, item.id);
1011         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
1012         encode_name(rbml_w, item.name);
1013         encode_attributes(rbml_w, &item.attrs);
1014         encode_repr_attrs(rbml_w, ecx, &item.attrs);
1015         for v in &enum_definition.variants {
1016             encode_variant_id(rbml_w, ecx.tcx.map.local_def_id(v.node.data.id()));
1017         }
1018         encode_inlined_item(ecx, rbml_w, InlinedItemRef::Item(item));
1019         encode_mir(ecx, rbml_w, item.id);
1020         encode_path(rbml_w, path);
1021
1022         // Encode inherent implementations for this enumeration.
1023         encode_inherent_implementations(ecx, rbml_w, def_id);
1024
1025         encode_visibility(rbml_w, vis);
1026         encode_stability(rbml_w, stab);
1027         encode_deprecation(rbml_w, depr);
1028         rbml_w.end_tag();
1029
1030         encode_enum_variant_info(ecx,
1031                                  rbml_w,
1032                                  def_id,
1033                                  vis,
1034                                  index);
1035       }
1036       hir::ItemStruct(ref struct_def, _) => {
1037         let def = ecx.tcx.lookup_adt_def(def_id);
1038         let variant = def.struct_variant();
1039
1040         /* Index the class*/
1041         index.record(def_id, rbml_w);
1042
1043         /* Now, make an item for the class itself */
1044         rbml_w.start_tag(tag_items_data_item);
1045         encode_def_id_and_key(ecx, rbml_w, def_id);
1046         encode_family(rbml_w, match *struct_def {
1047             hir::VariantData::Struct(..) => 'S',
1048             hir::VariantData::Tuple(..) => 's',
1049             hir::VariantData::Unit(..) => 'u',
1050         });
1051         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
1052
1053         encode_item_variances(rbml_w, ecx, item.id);
1054         encode_name(rbml_w, item.name);
1055         encode_attributes(rbml_w, &item.attrs);
1056         encode_path(rbml_w, path.clone());
1057         encode_stability(rbml_w, stab);
1058         encode_deprecation(rbml_w, depr);
1059         encode_visibility(rbml_w, vis);
1060         encode_repr_attrs(rbml_w, ecx, &item.attrs);
1061
1062         /* Encode def_ids for each field and method
1063          for methods, write all the stuff get_trait_method
1064         needs to know*/
1065         encode_struct_fields(rbml_w, variant);
1066
1067         encode_inlined_item(ecx, rbml_w, InlinedItemRef::Item(item));
1068         encode_mir(ecx, rbml_w, item.id);
1069
1070         // Encode inherent implementations for this structure.
1071         encode_inherent_implementations(ecx, rbml_w, def_id);
1072
1073         if !struct_def.is_struct() {
1074             let ctor_did = ecx.tcx.map.local_def_id(struct_def.id());
1075             rbml_w.wr_tagged_u64(tag_items_data_item_struct_ctor,
1076                                  def_to_u64(ctor_did));
1077         }
1078
1079         rbml_w.end_tag();
1080
1081         for field in &variant.fields {
1082             encode_field(ecx, rbml_w, field, index);
1083         }
1084
1085         // If this is a tuple-like struct, encode the type of the constructor.
1086         if !struct_def.is_struct() {
1087             encode_info_for_struct_ctor(ecx, rbml_w, item.name, struct_def, index, item.id);
1088         }
1089       }
1090       hir::ItemDefaultImpl(unsafety, _) => {
1091           index.record(def_id, rbml_w);
1092           rbml_w.start_tag(tag_items_data_item);
1093           encode_def_id_and_key(ecx, rbml_w, def_id);
1094           encode_family(rbml_w, 'd');
1095           encode_name(rbml_w, item.name);
1096           encode_unsafety(rbml_w, unsafety);
1097
1098           let trait_ref = tcx.impl_trait_ref(ecx.tcx.map.local_def_id(item.id)).unwrap();
1099           encode_trait_ref(rbml_w, ecx, trait_ref, tag_item_trait_ref);
1100           rbml_w.end_tag();
1101       }
1102       hir::ItemImpl(unsafety, polarity, _, _, _, ref ast_items) => {
1103         // We need to encode information about the default methods we
1104         // have inherited, so we drive this based on the impl structure.
1105         let impl_items = tcx.impl_items.borrow();
1106         let items = impl_items.get(&def_id).unwrap();
1107
1108         index.record(def_id, rbml_w);
1109         rbml_w.start_tag(tag_items_data_item);
1110         encode_def_id_and_key(ecx, rbml_w, def_id);
1111         encode_family(rbml_w, 'i');
1112         encode_bounds_and_type_for_item(rbml_w, ecx, index, item.id);
1113         encode_name(rbml_w, item.name);
1114         encode_attributes(rbml_w, &item.attrs);
1115         encode_unsafety(rbml_w, unsafety);
1116         encode_polarity(rbml_w, polarity);
1117
1118         match tcx.custom_coerce_unsized_kinds.borrow().get(&ecx.tcx.map.local_def_id(item.id)) {
1119             Some(&kind) => {
1120                 rbml_w.start_tag(tag_impl_coerce_unsized_kind);
1121                 kind.encode(rbml_w);
1122                 rbml_w.end_tag();
1123             }
1124             None => {}
1125         }
1126
1127         for &item_def_id in items {
1128             rbml_w.start_tag(tag_item_impl_item);
1129             match item_def_id {
1130                 ty::ConstTraitItemId(item_def_id) => {
1131                     encode_def_id(rbml_w, item_def_id);
1132                     encode_item_sort(rbml_w, 'C');
1133                 }
1134                 ty::MethodTraitItemId(item_def_id) => {
1135                     encode_def_id(rbml_w, item_def_id);
1136                     encode_item_sort(rbml_w, 'r');
1137                 }
1138                 ty::TypeTraitItemId(item_def_id) => {
1139                     encode_def_id(rbml_w, item_def_id);
1140                     encode_item_sort(rbml_w, 't');
1141                 }
1142             }
1143             rbml_w.end_tag();
1144         }
1145         let did = ecx.tcx.map.local_def_id(item.id);
1146         if let Some(trait_ref) = tcx.impl_trait_ref(did) {
1147             encode_trait_ref(rbml_w, ecx, trait_ref, tag_item_trait_ref);
1148
1149             let trait_def = tcx.lookup_trait_def(trait_ref.def_id);
1150             let parent = trait_def.ancestors(did)
1151                 .skip(1)
1152                 .next()
1153                 .and_then(|node| match node {
1154                     specialization_graph::Node::Impl(parent) => Some(parent),
1155                     _ => None,
1156                 });
1157             encode_parent_impl(rbml_w, parent);
1158         }
1159         encode_path(rbml_w, path.clone());
1160         encode_stability(rbml_w, stab);
1161         encode_deprecation(rbml_w, depr);
1162         rbml_w.end_tag();
1163
1164         // Iterate down the trait items, emitting them. We rely on the
1165         // assumption that all of the actually implemented trait items
1166         // appear first in the impl structure, in the same order they do
1167         // in the ast. This is a little sketchy.
1168         let num_implemented_methods = ast_items.len();
1169         for (i, &trait_item_def_id) in items.iter().enumerate() {
1170             let ast_item = if i < num_implemented_methods {
1171                 Some(&ast_items[i])
1172             } else {
1173                 None
1174             };
1175
1176             match tcx.impl_or_trait_item(trait_item_def_id.def_id()) {
1177                 ty::ConstTraitItem(ref associated_const) => {
1178                     encode_info_for_associated_const(ecx,
1179                                                      rbml_w,
1180                                                      index,
1181                                                      &associated_const,
1182                                                      path.clone(),
1183                                                      item.id,
1184                                                      ast_item)
1185                 }
1186                 ty::MethodTraitItem(ref method_type) => {
1187                     encode_info_for_method(ecx,
1188                                            rbml_w,
1189                                            index,
1190                                            &method_type,
1191                                            path.clone(),
1192                                            false,
1193                                            item.id,
1194                                            ast_item)
1195                 }
1196                 ty::TypeTraitItem(ref associated_type) => {
1197                     encode_info_for_associated_type(ecx,
1198                                                     rbml_w,
1199                                                     index,
1200                                                     &associated_type,
1201                                                     path.clone(),
1202                                                     item.id,
1203                                                     ast_item)
1204                 }
1205             }
1206         }
1207       }
1208       hir::ItemTrait(_, _, _, ref ms) => {
1209         index.record(def_id, rbml_w);
1210         rbml_w.start_tag(tag_items_data_item);
1211         encode_def_id_and_key(ecx, rbml_w, def_id);
1212         encode_family(rbml_w, 'I');
1213         encode_item_variances(rbml_w, ecx, item.id);
1214         let trait_def = tcx.lookup_trait_def(def_id);
1215         let trait_predicates = tcx.lookup_predicates(def_id);
1216         encode_unsafety(rbml_w, trait_def.unsafety);
1217         encode_paren_sugar(rbml_w, trait_def.paren_sugar);
1218         encode_defaulted(rbml_w, tcx.trait_has_default_impl(def_id));
1219         encode_associated_type_names(rbml_w, &trait_def.associated_type_names);
1220         encode_generics(rbml_w, ecx, index,
1221                         &trait_def.generics, &trait_predicates,
1222                         tag_item_generics);
1223         encode_predicates(rbml_w, ecx, index,
1224                           &tcx.lookup_super_predicates(def_id),
1225                           tag_item_super_predicates);
1226         encode_trait_ref(rbml_w, ecx, trait_def.trait_ref, tag_item_trait_ref);
1227         encode_name(rbml_w, item.name);
1228         encode_attributes(rbml_w, &item.attrs);
1229         encode_visibility(rbml_w, vis);
1230         encode_stability(rbml_w, stab);
1231         encode_deprecation(rbml_w, depr);
1232         for &method_def_id in tcx.trait_item_def_ids(def_id).iter() {
1233             rbml_w.start_tag(tag_item_trait_item);
1234             match method_def_id {
1235                 ty::ConstTraitItemId(const_def_id) => {
1236                     encode_def_id(rbml_w, const_def_id);
1237                     encode_item_sort(rbml_w, 'C');
1238                 }
1239                 ty::MethodTraitItemId(method_def_id) => {
1240                     encode_def_id(rbml_w, method_def_id);
1241                     encode_item_sort(rbml_w, 'r');
1242                 }
1243                 ty::TypeTraitItemId(type_def_id) => {
1244                     encode_def_id(rbml_w, type_def_id);
1245                     encode_item_sort(rbml_w, 't');
1246                 }
1247             }
1248             rbml_w.end_tag();
1249
1250             rbml_w.wr_tagged_u64(tag_mod_child,
1251                                  def_to_u64(method_def_id.def_id()));
1252         }
1253         encode_path(rbml_w, path.clone());
1254
1255         // Encode inherent implementations for this trait.
1256         encode_inherent_implementations(ecx, rbml_w, def_id);
1257
1258         rbml_w.end_tag();
1259
1260         // Now output the trait item info for each trait item.
1261         let r = tcx.trait_item_def_ids(def_id);
1262         for (i, &item_def_id) in r.iter().enumerate() {
1263             assert_eq!(item_def_id.def_id().krate, LOCAL_CRATE);
1264
1265             index.record(item_def_id.def_id(), rbml_w);
1266             rbml_w.start_tag(tag_items_data_item);
1267
1268             encode_parent_item(rbml_w, def_id);
1269
1270             let stab = stability::lookup_stability(tcx, item_def_id.def_id());
1271             let depr = stability::lookup_deprecation(tcx, item_def_id.def_id());
1272             encode_stability(rbml_w, stab);
1273             encode_deprecation(rbml_w, depr);
1274
1275             let trait_item_type =
1276                 tcx.impl_or_trait_item(item_def_id.def_id());
1277             let is_nonstatic_method;
1278             match trait_item_type {
1279                 ty::ConstTraitItem(associated_const) => {
1280                     encode_name(rbml_w, associated_const.name);
1281                     encode_def_id_and_key(ecx, rbml_w, associated_const.def_id);
1282                     encode_visibility(rbml_w, associated_const.vis);
1283
1284                     let elem = ast_map::PathName(associated_const.name);
1285                     encode_path(rbml_w,
1286                                 path.clone().chain(Some(elem)));
1287
1288                     encode_family(rbml_w, 'C');
1289
1290                     encode_bounds_and_type_for_item(rbml_w, ecx, index,
1291                                                     ecx.local_id(associated_const.def_id));
1292
1293                     is_nonstatic_method = false;
1294                 }
1295                 ty::MethodTraitItem(method_ty) => {
1296                     let method_def_id = item_def_id.def_id();
1297
1298                     encode_method_ty_fields(ecx, rbml_w, index, &method_ty);
1299
1300                     let elem = ast_map::PathName(method_ty.name);
1301                     encode_path(rbml_w,
1302                                 path.clone().chain(Some(elem)));
1303
1304                     match method_ty.explicit_self {
1305                         ty::ExplicitSelfCategory::Static => {
1306                             encode_family(rbml_w,
1307                                           STATIC_METHOD_FAMILY);
1308                         }
1309                         _ => {
1310                             encode_family(rbml_w,
1311                                           METHOD_FAMILY);
1312                         }
1313                     }
1314                     encode_bounds_and_type_for_item(rbml_w, ecx, index,
1315                                                     ecx.local_id(method_def_id));
1316
1317                     is_nonstatic_method = method_ty.explicit_self !=
1318                         ty::ExplicitSelfCategory::Static;
1319                 }
1320                 ty::TypeTraitItem(associated_type) => {
1321                     encode_name(rbml_w, associated_type.name);
1322                     encode_def_id_and_key(ecx, rbml_w, associated_type.def_id);
1323
1324                     let elem = ast_map::PathName(associated_type.name);
1325                     encode_path(rbml_w,
1326                                 path.clone().chain(Some(elem)));
1327
1328                     encode_item_sort(rbml_w, 't');
1329                     encode_family(rbml_w, 'y');
1330
1331                     if let Some(ty) = associated_type.ty {
1332                         encode_type(ecx, rbml_w, ty);
1333                     }
1334
1335                     is_nonstatic_method = false;
1336                 }
1337             }
1338
1339             let trait_item = &ms[i];
1340             encode_attributes(rbml_w, &trait_item.attrs);
1341             match trait_item.node {
1342                 hir::ConstTraitItem(_, ref default) => {
1343                     if default.is_some() {
1344                         encode_item_sort(rbml_w, 'C');
1345                     } else {
1346                         encode_item_sort(rbml_w, 'c');
1347                     }
1348
1349                     encode_inlined_item(ecx, rbml_w,
1350                                         InlinedItemRef::TraitItem(def_id, trait_item));
1351                     encode_mir(ecx, rbml_w, trait_item.id);
1352                 }
1353                 hir::MethodTraitItem(ref sig, ref body) => {
1354                     // If this is a static method, we've already
1355                     // encoded this.
1356                     if is_nonstatic_method {
1357                         // FIXME: I feel like there is something funny
1358                         // going on.
1359                         encode_bounds_and_type_for_item(rbml_w, ecx, index,
1360                                                         ecx.local_id(item_def_id.def_id()));
1361                     }
1362
1363                     if body.is_some() {
1364                         encode_item_sort(rbml_w, 'p');
1365                         encode_inlined_item(ecx, rbml_w,
1366                                             InlinedItemRef::TraitItem(def_id, trait_item));
1367                         encode_mir(ecx, rbml_w, trait_item.id);
1368                     } else {
1369                         encode_item_sort(rbml_w, 'r');
1370                     }
1371                     encode_method_argument_names(rbml_w, &sig.decl);
1372                 }
1373
1374                 hir::TypeTraitItem(..) => {}
1375             }
1376
1377             rbml_w.end_tag();
1378         }
1379       }
1380       hir::ItemExternCrate(_) | hir::ItemUse(_) => {
1381         // these are encoded separately
1382       }
1383     }
1384 }
1385
1386 fn encode_info_for_foreign_item<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
1387                                           rbml_w: &mut Encoder,
1388                                           nitem: &hir::ForeignItem,
1389                                           index: &mut CrateIndex<'tcx>,
1390                                           path: PathElems,
1391                                           abi: Abi) {
1392     let def_id = ecx.tcx.map.local_def_id(nitem.id);
1393
1394     index.record(def_id, rbml_w);
1395     rbml_w.start_tag(tag_items_data_item);
1396     encode_def_id_and_key(ecx, rbml_w, def_id);
1397     encode_visibility(rbml_w, nitem.vis);
1398     match nitem.node {
1399       hir::ForeignItemFn(ref fndecl, _) => {
1400         encode_family(rbml_w, FN_FAMILY);
1401         encode_bounds_and_type_for_item(rbml_w, ecx, index, nitem.id);
1402         encode_name(rbml_w, nitem.name);
1403         if abi == Abi::RustIntrinsic || abi == Abi::PlatformIntrinsic {
1404             encode_inlined_item(ecx, rbml_w, InlinedItemRef::Foreign(nitem));
1405             encode_mir(ecx, rbml_w, nitem.id);
1406         } else {
1407             encode_symbol(ecx, rbml_w, nitem.id);
1408         }
1409         encode_attributes(rbml_w, &nitem.attrs);
1410         let stab = stability::lookup_stability(ecx.tcx, ecx.tcx.map.local_def_id(nitem.id));
1411         let depr = stability::lookup_deprecation(ecx.tcx, ecx.tcx.map.local_def_id(nitem.id));
1412         encode_stability(rbml_w, stab);
1413         encode_deprecation(rbml_w, depr);
1414         encode_method_argument_names(rbml_w, &fndecl);
1415       }
1416       hir::ForeignItemStatic(_, mutbl) => {
1417         if mutbl {
1418             encode_family(rbml_w, 'b');
1419         } else {
1420             encode_family(rbml_w, 'c');
1421         }
1422         encode_bounds_and_type_for_item(rbml_w, ecx, index, nitem.id);
1423         encode_attributes(rbml_w, &nitem.attrs);
1424         let stab = stability::lookup_stability(ecx.tcx, ecx.tcx.map.local_def_id(nitem.id));
1425         let depr = stability::lookup_deprecation(ecx.tcx, ecx.tcx.map.local_def_id(nitem.id));
1426         encode_stability(rbml_w, stab);
1427         encode_deprecation(rbml_w, depr);
1428         encode_symbol(ecx, rbml_w, nitem.id);
1429         encode_name(rbml_w, nitem.name);
1430       }
1431     }
1432     encode_path(rbml_w, path);
1433     rbml_w.end_tag();
1434 }
1435
1436 fn my_visit_expr(expr: &hir::Expr,
1437                  rbml_w: &mut Encoder,
1438                  ecx: &EncodeContext,
1439                  index: &mut CrateIndex) {
1440     match expr.node {
1441         hir::ExprClosure(..) => {
1442             let def_id = ecx.tcx.map.local_def_id(expr.id);
1443
1444             index.record(def_id, rbml_w);
1445
1446             rbml_w.start_tag(tag_items_data_item);
1447             encode_def_id_and_key(ecx, rbml_w, def_id);
1448
1449             rbml_w.start_tag(tag_items_closure_ty);
1450             write_closure_type(ecx, rbml_w, &ecx.tcx.tables.borrow().closure_tys[&def_id]);
1451             rbml_w.end_tag();
1452
1453             rbml_w.start_tag(tag_items_closure_kind);
1454             ecx.tcx.closure_kind(def_id).encode(rbml_w).unwrap();
1455             rbml_w.end_tag();
1456
1457             ecx.tcx.map.with_path(expr.id, |path| encode_path(rbml_w, path));
1458
1459             assert!(ecx.mir_map.map.contains_key(&expr.id));
1460             encode_mir(ecx, rbml_w, expr.id);
1461
1462             rbml_w.end_tag();
1463         }
1464         _ => { }
1465     }
1466 }
1467
1468 fn my_visit_item<'a, 'tcx>(i: &hir::Item,
1469                            rbml_w: &mut Encoder,
1470                            ecx: &EncodeContext<'a, 'tcx>,
1471                            index: &mut CrateIndex<'tcx>) {
1472     ecx.tcx.map.with_path(i.id, |path| {
1473         encode_info_for_item(ecx, rbml_w, i, index, path, i.vis);
1474     });
1475 }
1476
1477 fn my_visit_foreign_item<'a, 'tcx>(ni: &hir::ForeignItem,
1478                                    rbml_w: &mut Encoder,
1479                                    ecx: &EncodeContext<'a, 'tcx>,
1480                                    index: &mut CrateIndex<'tcx>) {
1481     debug!("writing foreign item {}::{}",
1482             ecx.tcx.map.path_to_string(ni.id),
1483             ni.name);
1484
1485     let abi = ecx.tcx.map.get_foreign_abi(ni.id);
1486     ecx.tcx.map.with_path(ni.id, |path| {
1487         encode_info_for_foreign_item(ecx, rbml_w,
1488                                      ni, index,
1489                                      path, abi);
1490     });
1491 }
1492
1493 struct EncodeVisitor<'a, 'b:'a, 'c:'a, 'tcx:'c> {
1494     rbml_w_for_visit_item: &'a mut Encoder<'b>,
1495     ecx: &'a EncodeContext<'c,'tcx>,
1496     index: &'a mut CrateIndex<'tcx>,
1497 }
1498
1499 impl<'a, 'b, 'c, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'c, 'tcx> {
1500     fn visit_expr(&mut self, ex: &'tcx hir::Expr) {
1501         intravisit::walk_expr(self, ex);
1502         my_visit_expr(ex, self.rbml_w_for_visit_item, self.ecx, self.index);
1503     }
1504     fn visit_item(&mut self, i: &'tcx hir::Item) {
1505         intravisit::walk_item(self, i);
1506         my_visit_item(i, self.rbml_w_for_visit_item, self.ecx, self.index);
1507     }
1508     fn visit_foreign_item(&mut self, ni: &'tcx hir::ForeignItem) {
1509         intravisit::walk_foreign_item(self, ni);
1510         my_visit_foreign_item(ni, self.rbml_w_for_visit_item, self.ecx, self.index);
1511     }
1512 }
1513
1514 fn encode_info_for_items<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
1515                                    rbml_w: &mut Encoder)
1516                                    -> CrateIndex<'tcx> {
1517     let krate = ecx.tcx.map.krate();
1518
1519     let mut index = CrateIndex {
1520         items: IndexData::new(ecx.tcx.map.num_local_def_ids()),
1521         xrefs: FnvHashMap()
1522     };
1523     rbml_w.start_tag(tag_items_data);
1524
1525     index.record(DefId::local(CRATE_DEF_INDEX), rbml_w);
1526     encode_info_for_mod(ecx,
1527                         rbml_w,
1528                         &krate.module,
1529                         &[],
1530                         CRATE_NODE_ID,
1531                         [].iter().cloned().chain(LinkedPath::empty()),
1532                         syntax::parse::token::intern(&ecx.link_meta.crate_name),
1533                         hir::Public);
1534
1535     krate.visit_all_items(&mut EncodeVisitor {
1536         index: &mut index,
1537         ecx: ecx,
1538         rbml_w_for_visit_item: &mut *rbml_w,
1539     });
1540
1541     rbml_w.end_tag();
1542     index
1543 }
1544
1545 fn encode_item_index(rbml_w: &mut Encoder, index: IndexData) {
1546     rbml_w.start_tag(tag_index);
1547     index.write_index(rbml_w.writer);
1548     rbml_w.end_tag();
1549 }
1550
1551 fn encode_meta_item(rbml_w: &mut Encoder, mi: &ast::MetaItem) {
1552     match mi.node {
1553       ast::MetaItemKind::Word(ref name) => {
1554         rbml_w.start_tag(tag_meta_item_word);
1555         rbml_w.wr_tagged_str(tag_meta_item_name, name);
1556         rbml_w.end_tag();
1557       }
1558       ast::MetaItemKind::NameValue(ref name, ref value) => {
1559         match value.node {
1560           ast::LitKind::Str(ref value, _) => {
1561             rbml_w.start_tag(tag_meta_item_name_value);
1562             rbml_w.wr_tagged_str(tag_meta_item_name, name);
1563             rbml_w.wr_tagged_str(tag_meta_item_value, value);
1564             rbml_w.end_tag();
1565           }
1566           _ => {/* FIXME (#623): encode other variants */ }
1567         }
1568       }
1569       ast::MetaItemKind::List(ref name, ref items) => {
1570         rbml_w.start_tag(tag_meta_item_list);
1571         rbml_w.wr_tagged_str(tag_meta_item_name, name);
1572         for inner_item in items {
1573             encode_meta_item(rbml_w, &inner_item);
1574         }
1575         rbml_w.end_tag();
1576       }
1577     }
1578 }
1579
1580 fn encode_attributes(rbml_w: &mut Encoder, attrs: &[ast::Attribute]) {
1581     rbml_w.start_tag(tag_attributes);
1582     for attr in attrs {
1583         rbml_w.start_tag(tag_attribute);
1584         rbml_w.wr_tagged_u8(tag_attribute_is_sugared_doc, attr.node.is_sugared_doc as u8);
1585         encode_meta_item(rbml_w, &attr.node.value);
1586         rbml_w.end_tag();
1587     }
1588     rbml_w.end_tag();
1589 }
1590
1591 fn encode_unsafety(rbml_w: &mut Encoder, unsafety: hir::Unsafety) {
1592     let byte: u8 = match unsafety {
1593         hir::Unsafety::Normal => 0,
1594         hir::Unsafety::Unsafe => 1,
1595     };
1596     rbml_w.wr_tagged_u8(tag_unsafety, byte);
1597 }
1598
1599 fn encode_paren_sugar(rbml_w: &mut Encoder, paren_sugar: bool) {
1600     let byte: u8 = if paren_sugar {1} else {0};
1601     rbml_w.wr_tagged_u8(tag_paren_sugar, byte);
1602 }
1603
1604 fn encode_defaulted(rbml_w: &mut Encoder, is_defaulted: bool) {
1605     let byte: u8 = if is_defaulted {1} else {0};
1606     rbml_w.wr_tagged_u8(tag_defaulted_trait, byte);
1607 }
1608
1609 fn encode_associated_type_names(rbml_w: &mut Encoder, names: &[Name]) {
1610     rbml_w.start_tag(tag_associated_type_names);
1611     for &name in names {
1612         rbml_w.wr_tagged_str(tag_associated_type_name, &name.as_str());
1613     }
1614     rbml_w.end_tag();
1615 }
1616
1617 fn encode_polarity(rbml_w: &mut Encoder, polarity: hir::ImplPolarity) {
1618     let byte: u8 = match polarity {
1619         hir::ImplPolarity::Positive => 0,
1620         hir::ImplPolarity::Negative => 1,
1621     };
1622     rbml_w.wr_tagged_u8(tag_polarity, byte);
1623 }
1624
1625 fn encode_crate_deps(rbml_w: &mut Encoder, cstore: &cstore::CStore) {
1626     fn get_ordered_deps(cstore: &cstore::CStore)
1627                         -> Vec<(CrateNum, Rc<cstore::crate_metadata>)> {
1628         // Pull the cnums and name,vers,hash out of cstore
1629         let mut deps = Vec::new();
1630         cstore.iter_crate_data(|cnum, val| {
1631             deps.push((cnum, val.clone()));
1632         });
1633
1634         // Sort by cnum
1635         deps.sort_by(|kv1, kv2| kv1.0.cmp(&kv2.0));
1636
1637         // Sanity-check the crate numbers
1638         let mut expected_cnum = 1;
1639         for &(n, _) in &deps {
1640             assert_eq!(n, expected_cnum);
1641             expected_cnum += 1;
1642         }
1643
1644         deps
1645     }
1646
1647     // We're just going to write a list of crate 'name-hash-version's, with
1648     // the assumption that they are numbered 1 to n.
1649     // FIXME (#2166): This is not nearly enough to support correct versioning
1650     // but is enough to get transitive crate dependencies working.
1651     rbml_w.start_tag(tag_crate_deps);
1652     for (_cnum, dep) in get_ordered_deps(cstore) {
1653         encode_crate_dep(rbml_w, &dep);
1654     }
1655     rbml_w.end_tag();
1656 }
1657
1658 fn encode_lang_items(ecx: &EncodeContext, rbml_w: &mut Encoder) {
1659     rbml_w.start_tag(tag_lang_items);
1660
1661     for (i, &opt_def_id) in ecx.tcx.lang_items.items().iter().enumerate() {
1662         if let Some(def_id) = opt_def_id {
1663             if def_id.is_local() {
1664                 rbml_w.start_tag(tag_lang_items_item);
1665                 rbml_w.wr_tagged_u32(tag_lang_items_item_id, i as u32);
1666                 rbml_w.wr_tagged_u32(tag_lang_items_item_index, def_id.index.as_u32());
1667                 rbml_w.end_tag();
1668             }
1669         }
1670     }
1671
1672     for i in &ecx.tcx.lang_items.missing {
1673         rbml_w.wr_tagged_u32(tag_lang_items_missing, *i as u32);
1674     }
1675
1676     rbml_w.end_tag();   // tag_lang_items
1677 }
1678
1679 fn encode_native_libraries(ecx: &EncodeContext, rbml_w: &mut Encoder) {
1680     rbml_w.start_tag(tag_native_libraries);
1681
1682     for &(ref lib, kind) in ecx.tcx.sess.cstore.used_libraries().iter() {
1683         match kind {
1684             cstore::NativeStatic => {} // these libraries are not propagated
1685             cstore::NativeFramework | cstore::NativeUnknown => {
1686                 rbml_w.start_tag(tag_native_libraries_lib);
1687                 rbml_w.wr_tagged_u32(tag_native_libraries_kind, kind as u32);
1688                 rbml_w.wr_tagged_str(tag_native_libraries_name, lib);
1689                 rbml_w.end_tag();
1690             }
1691         }
1692     }
1693
1694     rbml_w.end_tag();
1695 }
1696
1697 fn encode_plugin_registrar_fn(ecx: &EncodeContext, rbml_w: &mut Encoder) {
1698     match ecx.tcx.sess.plugin_registrar_fn.get() {
1699         Some(id) => {
1700             let def_id = ecx.tcx.map.local_def_id(id);
1701             rbml_w.wr_tagged_u32(tag_plugin_registrar_fn, def_id.index.as_u32());
1702         }
1703         None => {}
1704     }
1705 }
1706
1707 fn encode_codemap(ecx: &EncodeContext, rbml_w: &mut Encoder) {
1708     rbml_w.start_tag(tag_codemap);
1709     let codemap = ecx.tcx.sess.codemap();
1710
1711     for filemap in &codemap.files.borrow()[..] {
1712
1713         if filemap.lines.borrow().is_empty() || filemap.is_imported() {
1714             // No need to export empty filemaps, as they can't contain spans
1715             // that need translation.
1716             // Also no need to re-export imported filemaps, as any downstream
1717             // crate will import them from their original source.
1718             continue;
1719         }
1720
1721         rbml_w.start_tag(tag_codemap_filemap);
1722         rbml_w.emit_opaque(|opaque_encoder| {
1723             filemap.encode(opaque_encoder)
1724         }).unwrap();
1725         rbml_w.end_tag();
1726     }
1727
1728     rbml_w.end_tag();
1729 }
1730
1731 /// Serialize the text of the exported macros
1732 fn encode_macro_defs(rbml_w: &mut Encoder,
1733                      krate: &hir::Crate) {
1734     rbml_w.start_tag(tag_macro_defs);
1735     for def in &krate.exported_macros {
1736         rbml_w.start_tag(tag_macro_def);
1737
1738         encode_name(rbml_w, def.name);
1739         encode_attributes(rbml_w, &def.attrs);
1740         let &BytePos(lo) = &def.span.lo;
1741         let &BytePos(hi) = &def.span.hi;
1742         rbml_w.wr_tagged_u32(tag_macro_def_span_lo, lo);
1743         rbml_w.wr_tagged_u32(tag_macro_def_span_hi, hi);
1744
1745         rbml_w.wr_tagged_str(tag_macro_def_body,
1746                              &::syntax::print::pprust::tts_to_string(&def.body));
1747
1748         rbml_w.end_tag();
1749     }
1750     rbml_w.end_tag();
1751 }
1752
1753 fn encode_struct_field_attrs(ecx: &EncodeContext,
1754                              rbml_w: &mut Encoder,
1755                              krate: &hir::Crate) {
1756     struct StructFieldVisitor<'a, 'b:'a, 'c:'a, 'tcx:'b> {
1757         ecx: &'a EncodeContext<'b, 'tcx>,
1758         rbml_w: &'a mut Encoder<'c>,
1759     }
1760
1761     impl<'a, 'b, 'c, 'tcx, 'v> Visitor<'v> for StructFieldVisitor<'a, 'b, 'c, 'tcx> {
1762         fn visit_struct_field(&mut self, field: &hir::StructField) {
1763             self.rbml_w.start_tag(tag_struct_field);
1764             let def_id = self.ecx.tcx.map.local_def_id(field.id);
1765             encode_def_id(self.rbml_w, def_id);
1766             encode_attributes(self.rbml_w, &field.attrs);
1767             self.rbml_w.end_tag();
1768         }
1769     }
1770
1771     rbml_w.start_tag(tag_struct_fields);
1772     krate.visit_all_items(&mut StructFieldVisitor { ecx: ecx, rbml_w: rbml_w });
1773     rbml_w.end_tag();
1774 }
1775
1776
1777
1778 struct ImplVisitor<'a, 'tcx:'a> {
1779     tcx: &'a TyCtxt<'tcx>,
1780     impls: FnvHashMap<DefId, Vec<DefId>>
1781 }
1782
1783 impl<'a, 'tcx, 'v> Visitor<'v> for ImplVisitor<'a, 'tcx> {
1784     fn visit_item(&mut self, item: &hir::Item) {
1785         if let hir::ItemImpl(..) = item.node {
1786             let impl_id = self.tcx.map.local_def_id(item.id);
1787             if let Some(trait_ref) = self.tcx.impl_trait_ref(impl_id) {
1788                 self.impls.entry(trait_ref.def_id)
1789                     .or_insert(vec![])
1790                     .push(impl_id);
1791             }
1792         }
1793     }
1794 }
1795
1796 /// Encodes an index, mapping each trait to its (local) implementations.
1797 fn encode_impls<'a>(ecx: &'a EncodeContext,
1798                     krate: &hir::Crate,
1799                     rbml_w: &'a mut Encoder) {
1800     let mut visitor = ImplVisitor {
1801         tcx: ecx.tcx,
1802         impls: FnvHashMap()
1803     };
1804     krate.visit_all_items(&mut visitor);
1805
1806     rbml_w.start_tag(tag_impls);
1807     for (trait_, trait_impls) in visitor.impls {
1808         rbml_w.start_tag(tag_impls_trait);
1809         encode_def_id(rbml_w, trait_);
1810         for impl_ in trait_impls {
1811             rbml_w.wr_tagged_u64(tag_impls_trait_impl, def_to_u64(impl_));
1812         }
1813         rbml_w.end_tag();
1814     }
1815     rbml_w.end_tag();
1816 }
1817
1818 fn encode_misc_info(ecx: &EncodeContext,
1819                     krate: &hir::Crate,
1820                     rbml_w: &mut Encoder) {
1821     rbml_w.start_tag(tag_misc_info);
1822     rbml_w.start_tag(tag_misc_info_crate_items);
1823     for item_id in &krate.module.item_ids {
1824         rbml_w.wr_tagged_u64(tag_mod_child,
1825                              def_to_u64(ecx.tcx.map.local_def_id(item_id.id)));
1826
1827         let item = ecx.tcx.map.expect_item(item_id.id);
1828         each_auxiliary_node_id(item, |auxiliary_node_id| {
1829             rbml_w.wr_tagged_u64(tag_mod_child,
1830                                  def_to_u64(ecx.tcx.map.local_def_id(auxiliary_node_id)));
1831             true
1832         });
1833     }
1834
1835     // Encode reexports for the root module.
1836     encode_reexports(ecx, rbml_w, 0);
1837
1838     rbml_w.end_tag();
1839     rbml_w.end_tag();
1840 }
1841
1842 // Encodes all reachable symbols in this crate into the metadata.
1843 //
1844 // This pass is seeded off the reachability list calculated in the
1845 // middle::reachable module but filters out items that either don't have a
1846 // symbol associated with them (they weren't translated) or if they're an FFI
1847 // definition (as that's not defined in this crate).
1848 fn encode_reachable(ecx: &EncodeContext, rbml_w: &mut Encoder) {
1849     rbml_w.start_tag(tag_reachable_ids);
1850     for &id in ecx.reachable {
1851         let def_id = ecx.tcx.map.local_def_id(id);
1852         rbml_w.wr_tagged_u32(tag_reachable_id, def_id.index.as_u32());
1853     }
1854     rbml_w.end_tag();
1855 }
1856
1857 fn encode_crate_dep(rbml_w: &mut Encoder,
1858                     dep: &cstore::crate_metadata) {
1859     rbml_w.start_tag(tag_crate_dep);
1860     rbml_w.wr_tagged_str(tag_crate_dep_crate_name, &dep.name());
1861     let hash = decoder::get_crate_hash(dep.data());
1862     rbml_w.wr_tagged_str(tag_crate_dep_hash, hash.as_str());
1863     rbml_w.wr_tagged_u8(tag_crate_dep_explicitly_linked,
1864                         dep.explicitly_linked.get() as u8);
1865     rbml_w.end_tag();
1866 }
1867
1868 fn encode_hash(rbml_w: &mut Encoder, hash: &Svh) {
1869     rbml_w.wr_tagged_str(tag_crate_hash, hash.as_str());
1870 }
1871
1872 fn encode_rustc_version(rbml_w: &mut Encoder) {
1873     rbml_w.wr_tagged_str(tag_rustc_version, &rustc_version());
1874 }
1875
1876 fn encode_crate_name(rbml_w: &mut Encoder, crate_name: &str) {
1877     rbml_w.wr_tagged_str(tag_crate_crate_name, crate_name);
1878 }
1879
1880 fn encode_crate_disambiguator(rbml_w: &mut Encoder, crate_disambiguator: &str) {
1881     rbml_w.wr_tagged_str(tag_crate_disambiguator, crate_disambiguator);
1882 }
1883
1884 fn encode_crate_triple(rbml_w: &mut Encoder, triple: &str) {
1885     rbml_w.wr_tagged_str(tag_crate_triple, triple);
1886 }
1887
1888 fn encode_dylib_dependency_formats(rbml_w: &mut Encoder, ecx: &EncodeContext) {
1889     let tag = tag_dylib_dependency_formats;
1890     match ecx.tcx.sess.dependency_formats.borrow().get(&config::CrateTypeDylib) {
1891         Some(arr) => {
1892             let s = arr.iter().enumerate().filter_map(|(i, slot)| {
1893                 let kind = match *slot {
1894                     Linkage::NotLinked |
1895                     Linkage::IncludedFromDylib => return None,
1896                     Linkage::Dynamic => "d",
1897                     Linkage::Static => "s",
1898                 };
1899                 Some(format!("{}:{}", i + 1, kind))
1900             }).collect::<Vec<String>>();
1901             rbml_w.wr_tagged_str(tag, &s.join(","));
1902         }
1903         None => {
1904             rbml_w.wr_tagged_str(tag, "");
1905         }
1906     }
1907 }
1908
1909 // NB: Increment this as you change the metadata encoding version.
1910 #[allow(non_upper_case_globals)]
1911 pub const metadata_encoding_version : &'static [u8] = &[b'r', b'u', b's', b't', 0, 0, 0, 2 ];
1912
1913 pub fn encode_metadata(ecx: EncodeContext, krate: &hir::Crate) -> Vec<u8> {
1914     let mut wr = Cursor::new(Vec::new());
1915
1916     {
1917         let mut rbml_w = Encoder::new(&mut wr);
1918         encode_metadata_inner(&mut rbml_w, &ecx, krate)
1919     }
1920
1921     // RBML compacts the encoded bytes whenever appropriate,
1922     // so there are some garbages left after the end of the data.
1923     let metalen = wr.seek(SeekFrom::Current(0)).unwrap() as usize;
1924     let mut v = wr.into_inner();
1925     v.truncate(metalen);
1926     assert_eq!(v.len(), metalen);
1927
1928     // And here we run into yet another obscure archive bug: in which metadata
1929     // loaded from archives may have trailing garbage bytes. Awhile back one of
1930     // our tests was failing sporadically on the OSX 64-bit builders (both nopt
1931     // and opt) by having rbml generate an out-of-bounds panic when looking at
1932     // metadata.
1933     //
1934     // Upon investigation it turned out that the metadata file inside of an rlib
1935     // (and ar archive) was being corrupted. Some compilations would generate a
1936     // metadata file which would end in a few extra bytes, while other
1937     // compilations would not have these extra bytes appended to the end. These
1938     // extra bytes were interpreted by rbml as an extra tag, so they ended up
1939     // being interpreted causing the out-of-bounds.
1940     //
1941     // The root cause of why these extra bytes were appearing was never
1942     // discovered, and in the meantime the solution we're employing is to insert
1943     // the length of the metadata to the start of the metadata. Later on this
1944     // will allow us to slice the metadata to the precise length that we just
1945     // generated regardless of trailing bytes that end up in it.
1946     let len = v.len() as u32;
1947     v.insert(0, (len >>  0) as u8);
1948     v.insert(0, (len >>  8) as u8);
1949     v.insert(0, (len >> 16) as u8);
1950     v.insert(0, (len >> 24) as u8);
1951     return v;
1952 }
1953
1954 fn encode_metadata_inner(rbml_w: &mut Encoder,
1955                          ecx: &EncodeContext,
1956                          krate: &hir::Crate) {
1957     struct Stats {
1958         attr_bytes: u64,
1959         dep_bytes: u64,
1960         lang_item_bytes: u64,
1961         native_lib_bytes: u64,
1962         plugin_registrar_fn_bytes: u64,
1963         codemap_bytes: u64,
1964         macro_defs_bytes: u64,
1965         impl_bytes: u64,
1966         misc_bytes: u64,
1967         item_bytes: u64,
1968         index_bytes: u64,
1969         xref_bytes: u64,
1970         zero_bytes: u64,
1971         total_bytes: u64,
1972     }
1973     let mut stats = Stats {
1974         attr_bytes: 0,
1975         dep_bytes: 0,
1976         lang_item_bytes: 0,
1977         native_lib_bytes: 0,
1978         plugin_registrar_fn_bytes: 0,
1979         codemap_bytes: 0,
1980         macro_defs_bytes: 0,
1981         impl_bytes: 0,
1982         misc_bytes: 0,
1983         item_bytes: 0,
1984         index_bytes: 0,
1985         xref_bytes: 0,
1986         zero_bytes: 0,
1987         total_bytes: 0,
1988     };
1989
1990     encode_rustc_version(rbml_w);
1991     encode_crate_name(rbml_w, &ecx.link_meta.crate_name);
1992     encode_crate_triple(rbml_w, &ecx.tcx.sess.opts.target_triple);
1993     encode_hash(rbml_w, &ecx.link_meta.crate_hash);
1994     encode_crate_disambiguator(rbml_w, &ecx.tcx.sess.crate_disambiguator.borrow());
1995     encode_dylib_dependency_formats(rbml_w, &ecx);
1996
1997     let mut i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
1998     encode_attributes(rbml_w, &krate.attrs);
1999     stats.attr_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2000
2001     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2002     encode_crate_deps(rbml_w, ecx.cstore);
2003     stats.dep_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2004
2005     // Encode the language items.
2006     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2007     encode_lang_items(&ecx, rbml_w);
2008     stats.lang_item_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2009
2010     // Encode the native libraries used
2011     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2012     encode_native_libraries(&ecx, rbml_w);
2013     stats.native_lib_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2014
2015     // Encode the plugin registrar function
2016     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2017     encode_plugin_registrar_fn(&ecx, rbml_w);
2018     stats.plugin_registrar_fn_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2019
2020     // Encode codemap
2021     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2022     encode_codemap(&ecx, rbml_w);
2023     stats.codemap_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2024
2025     // Encode macro definitions
2026     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2027     encode_macro_defs(rbml_w, krate);
2028     stats.macro_defs_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2029
2030     // Encode the def IDs of impls, for coherence checking.
2031     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2032     encode_impls(&ecx, krate, rbml_w);
2033     stats.impl_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2034
2035     // Encode miscellaneous info.
2036     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2037     encode_misc_info(&ecx, krate, rbml_w);
2038     encode_reachable(&ecx, rbml_w);
2039     stats.misc_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2040
2041     // Encode and index the items.
2042     rbml_w.start_tag(tag_items);
2043     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2044     let index = encode_info_for_items(&ecx, rbml_w);
2045     stats.item_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2046     rbml_w.end_tag();
2047
2048     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2049     encode_item_index(rbml_w, index.items);
2050     stats.index_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2051
2052     i = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2053     encode_xrefs(&ecx, rbml_w, index.xrefs);
2054     stats.xref_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap() - i;
2055
2056     encode_struct_field_attrs(&ecx, rbml_w, krate);
2057
2058     stats.total_bytes = rbml_w.writer.seek(SeekFrom::Current(0)).unwrap();
2059
2060     if ecx.tcx.sess.meta_stats() {
2061         for e in rbml_w.writer.get_ref() {
2062             if *e == 0 {
2063                 stats.zero_bytes += 1;
2064             }
2065         }
2066
2067         println!("metadata stats:");
2068         println!("       attribute bytes: {}", stats.attr_bytes);
2069         println!("             dep bytes: {}", stats.dep_bytes);
2070         println!("       lang item bytes: {}", stats.lang_item_bytes);
2071         println!("          native bytes: {}", stats.native_lib_bytes);
2072         println!("plugin registrar bytes: {}", stats.plugin_registrar_fn_bytes);
2073         println!("         codemap bytes: {}", stats.codemap_bytes);
2074         println!("       macro def bytes: {}", stats.macro_defs_bytes);
2075         println!("            impl bytes: {}", stats.impl_bytes);
2076         println!("            misc bytes: {}", stats.misc_bytes);
2077         println!("            item bytes: {}", stats.item_bytes);
2078         println!("           index bytes: {}", stats.index_bytes);
2079         println!("            xref bytes: {}", stats.xref_bytes);
2080         println!("            zero bytes: {}", stats.zero_bytes);
2081         println!("           total bytes: {}", stats.total_bytes);
2082     }
2083 }
2084
2085 // Get the encoded string for a type
2086 pub fn encoded_ty<'tcx>(tcx: &TyCtxt<'tcx>,
2087                         t: Ty<'tcx>,
2088                         def_id_to_string: fn(&TyCtxt<'tcx>, DefId) -> String)
2089                         -> Vec<u8> {
2090     let mut wr = Cursor::new(Vec::new());
2091     tyencode::enc_ty(&mut wr, &tyencode::ctxt {
2092         diag: tcx.sess.diagnostic(),
2093         ds: def_id_to_string,
2094         tcx: tcx,
2095         abbrevs: &RefCell::new(FnvHashMap())
2096     }, t);
2097     wr.into_inner()
2098 }