src/librustc/metadata/encoder.rs

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