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