src/librustc/metadata/encoder.rs

   1 // Copyright 2012 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
  14 use metadata::common::*;
  15 use metadata::cstore;
  16 use metadata::decoder;
  17 use metadata::tyencode;
  18 use middle::ty::{node_id_to_type, lookup_item_type};
  19 use middle::ty;
  20 use middle;
  21
  22 use std::hash::HashUtil;
  23 use std::hashmap::{HashMap, HashSet};
  24 use std::int;
  25 use std::io;
  26 use std::str;
  27 use std::uint;
  28 use std::vec;
  29 use extra::flate;
  30 use extra::serialize::Encodable;
  31 use extra;
  32 use syntax::abi::AbiSet;
  33 use syntax::ast::*;
  34 use syntax::ast;
  35 use syntax::ast_map;
  36 use syntax::ast_util::*;
  37 use syntax::attr;
  38 use syntax::attr::AttrMetaMethods;
  39 use syntax::diagnostic::span_handler;
  40 use syntax::parse::token::special_idents;
  41 use syntax::{ast_util, visit};
  42 use syntax::parse::token;
  43 use syntax;
  44 use writer = extra::ebml::writer;
  45
  46 use std::cast;
  47
  48 // used by astencode:
  49 type abbrev_map = @mut HashMap<ty::t, tyencode::ty_abbrev>;
  50
  51 pub type encode_inlined_item<'self> = &'self fn(ecx: &EncodeContext,
  52                                    ebml_w: &mut writer::Encoder,
  53                                    path: &[ast_map::path_elt],
  54                                    ii: ast::inlined_item);
  55
  56 pub struct EncodeParams<'self> {
  57     diag: @span_handler,
  58     tcx: ty::ctxt,
  59     reexports2: middle::resolve::ExportMap2,
  60     item_symbols: &'self HashMap<ast::node_id, ~str>,
  61     discrim_symbols: &'self HashMap<ast::node_id, @str>,
  62     link_meta: &'self LinkMeta,
  63     cstore: @mut cstore::CStore,
  64     encode_inlined_item: encode_inlined_item<'self>,
  65     reachable: @mut HashSet<ast::node_id>,
  66 }
  67
  68 struct Stats {
  69     inline_bytes: uint,
  70     attr_bytes: uint,
  71     dep_bytes: uint,
  72     lang_item_bytes: uint,
  73     link_args_bytes: uint,
  74     misc_bytes: uint,
  75     item_bytes: uint,
  76     index_bytes: uint,
  77     zero_bytes: uint,
  78     total_bytes: uint,
  79
  80     n_inlines: uint
  81 }
  82
  83 pub struct EncodeContext<'self> {
  84     diag: @span_handler,
  85     tcx: ty::ctxt,
  86     stats: @mut Stats,
  87     reexports2: middle::resolve::ExportMap2,
  88     item_symbols: &'self HashMap<ast::node_id, ~str>,
  89     discrim_symbols: &'self HashMap<ast::node_id, @str>,
  90     link_meta: &'self LinkMeta,
  91     cstore: &'self cstore::CStore,
  92     encode_inlined_item: encode_inlined_item<'self>,
  93     type_abbrevs: abbrev_map,
  94     reachable: @mut HashSet<ast::node_id>,
  95 }
  96
  97 pub fn reachable(ecx: &EncodeContext, id: node_id) -> bool {
  98     ecx.reachable.contains(&id)
  99 }
 100
 101 fn encode_name(ecx: &EncodeContext,
 102                ebml_w: &mut writer::Encoder,
 103                name: ident) {
 104     ebml_w.wr_tagged_str(tag_paths_data_name, ecx.tcx.sess.str_of(name));
 105 }
 106
 107 fn encode_impl_type_basename(ecx: &EncodeContext,
 108                              ebml_w: &mut writer::Encoder,
 109                              name: ident) {
 110     ebml_w.wr_tagged_str(tag_item_impl_type_basename,
 111                          ecx.tcx.sess.str_of(name));
 112 }
 113
 114 pub fn encode_def_id(ebml_w: &mut writer::Encoder, id: def_id) {
 115     ebml_w.wr_tagged_str(tag_def_id, def_to_str(id));
 116 }
 117
 118 fn encode_region_param(ecx: &EncodeContext,
 119                        ebml_w: &mut writer::Encoder,
 120                        it: @ast::item) {
 121     let opt_rp = ecx.tcx.region_paramd_items.find(&it.id);
 122     for opt_rp.iter().advance |rp| {
 123         ebml_w.start_tag(tag_region_param);
 124         rp.encode(ebml_w);
 125         ebml_w.end_tag();
 126     }
 127 }
 128
 129 #[deriving(Clone)]
 130 struct entry<T> {
 131     val: T,
 132     pos: uint
 133 }
 134
 135 fn add_to_index(ebml_w: &mut writer::Encoder,
 136                 path: &[ident],
 137                 index: &mut ~[entry<~str>],
 138                 name: ident) {
 139     let mut full_path = ~[];
 140     full_path.push_all(path);
 141     full_path.push(name);
 142     index.push(
 143         entry {
 144             val: ast_util::path_name_i(full_path),
 145             pos: ebml_w.writer.tell()
 146         });
 147 }
 148
 149 fn encode_trait_ref(ebml_w: &mut writer::Encoder,
 150                     ecx: &EncodeContext,
 151                     trait_ref: &ty::TraitRef,
 152                     tag: uint) {
 153     let ty_str_ctxt = @tyencode::ctxt {
 154         diag: ecx.diag,
 155         ds: def_to_str,
 156         tcx: ecx.tcx,
 157         abbrevs: tyencode::ac_use_abbrevs(ecx.type_abbrevs)
 158     };
 159
 160     ebml_w.start_tag(tag);
 161     tyencode::enc_trait_ref(ebml_w.writer, ty_str_ctxt, trait_ref);
 162     ebml_w.end_tag();
 163 }
 164
 165 // Item info table encoding
 166 fn encode_family(ebml_w: &mut writer::Encoder, c: char) {
 167     ebml_w.start_tag(tag_items_data_item_family);
 168     ebml_w.writer.write(&[c as u8]);
 169     ebml_w.end_tag();
 170 }
 171
 172 pub fn def_to_str(did: def_id) -> ~str {
 173     fmt!("%d:%d", did.crate, did.node)
 174 }
 175
 176 fn encode_ty_type_param_defs(ebml_w: &mut writer::Encoder,
 177                              ecx: &EncodeContext,
 178                              params: @~[ty::TypeParameterDef],
 179                              tag: uint) {
 180     let ty_str_ctxt = @tyencode::ctxt {
 181         diag: ecx.diag,
 182         ds: def_to_str,
 183         tcx: ecx.tcx,
 184         abbrevs: tyencode::ac_use_abbrevs(ecx.type_abbrevs)
 185     };
 186     for params.iter().advance |param| {
 187         ebml_w.start_tag(tag);
 188         tyencode::enc_type_param_def(ebml_w.writer, ty_str_ctxt, param);
 189         ebml_w.end_tag();
 190     }
 191 }
 192
 193 fn encode_bounds_and_type(ebml_w: &mut writer::Encoder,
 194                           ecx: &EncodeContext,
 195                           tpt: &ty::ty_param_bounds_and_ty) {
 196     encode_ty_type_param_defs(ebml_w, ecx, tpt.generics.type_param_defs,
 197                               tag_items_data_item_ty_param_bounds);
 198     encode_type(ecx, ebml_w, tpt.ty);
 199 }
 200
 201 fn encode_variant_id(ebml_w: &mut writer::Encoder, vid: def_id) {
 202     ebml_w.start_tag(tag_items_data_item_variant);
 203     let s = def_to_str(vid);
 204     ebml_w.writer.write(s.as_bytes());
 205     ebml_w.end_tag();
 206 }
 207
 208 pub fn write_type(ecx: &EncodeContext,
 209                   ebml_w: &mut writer::Encoder,
 210                   typ: ty::t) {
 211     let ty_str_ctxt = @tyencode::ctxt {
 212         diag: ecx.diag,
 213         ds: def_to_str,
 214         tcx: ecx.tcx,
 215         abbrevs: tyencode::ac_use_abbrevs(ecx.type_abbrevs)
 216     };
 217     tyencode::enc_ty(ebml_w.writer, ty_str_ctxt, typ);
 218 }
 219
 220 pub fn write_vstore(ecx: &EncodeContext,
 221                     ebml_w: &mut writer::Encoder,
 222                     vstore: ty::vstore) {
 223     let ty_str_ctxt = @tyencode::ctxt {
 224         diag: ecx.diag,
 225         ds: def_to_str,
 226         tcx: ecx.tcx,
 227         abbrevs: tyencode::ac_use_abbrevs(ecx.type_abbrevs)
 228     };
 229     tyencode::enc_vstore(ebml_w.writer, ty_str_ctxt, vstore);
 230 }
 231
 232 fn encode_type(ecx: &EncodeContext,
 233                ebml_w: &mut writer::Encoder,
 234                typ: ty::t) {
 235     ebml_w.start_tag(tag_items_data_item_type);
 236     write_type(ecx, ebml_w, typ);
 237     ebml_w.end_tag();
 238 }
 239
 240 fn encode_transformed_self_ty(ecx: &EncodeContext,
 241                               ebml_w: &mut writer::Encoder,
 242                               opt_typ: Option<ty::t>) {
 243     for opt_typ.iter().advance |&typ| {
 244         ebml_w.start_tag(tag_item_method_transformed_self_ty);
 245         write_type(ecx, ebml_w, typ);
 246         ebml_w.end_tag();
 247     }
 248 }
 249
 250 fn encode_method_fty(ecx: &EncodeContext,
 251                      ebml_w: &mut writer::Encoder,
 252                      typ: &ty::BareFnTy) {
 253     ebml_w.start_tag(tag_item_method_fty);
 254
 255     let ty_str_ctxt = @tyencode::ctxt {
 256         diag: ecx.diag,
 257         ds: def_to_str,
 258         tcx: ecx.tcx,
 259         abbrevs: tyencode::ac_use_abbrevs(ecx.type_abbrevs)
 260     };
 261     tyencode::enc_bare_fn_ty(ebml_w.writer, ty_str_ctxt, typ);
 262
 263     ebml_w.end_tag();
 264 }
 265
 266 fn encode_symbol(ecx: &EncodeContext,
 267                  ebml_w: &mut writer::Encoder,
 268                  id: node_id) {
 269     ebml_w.start_tag(tag_items_data_item_symbol);
 270     match ecx.item_symbols.find(&id) {
 271         Some(x) => {
 272             debug!("encode_symbol(id=%?, str=%s)", id, *x);
 273             ebml_w.writer.write(x.as_bytes());
 274         }
 275         None => {
 276             ecx.diag.handler().bug(
 277                 fmt!("encode_symbol: id not found %d", id));
 278         }
 279     }
 280     ebml_w.end_tag();
 281 }
 282
 283 fn encode_discriminant(ecx: &EncodeContext,
 284                        ebml_w: &mut writer::Encoder,
 285                        id: node_id) {
 286     ebml_w.start_tag(tag_items_data_item_symbol);
 287     ebml_w.writer.write(ecx.discrim_symbols.get_copy(&id).as_bytes());
 288     ebml_w.end_tag();
 289 }
 290
 291 fn encode_disr_val(_: &EncodeContext,
 292                    ebml_w: &mut writer::Encoder,
 293                    disr_val: int) {
 294     ebml_w.start_tag(tag_disr_val);
 295     let s = int::to_str(disr_val);
 296     ebml_w.writer.write(s.as_bytes());
 297     ebml_w.end_tag();
 298 }
 299
 300 fn encode_parent_item(ebml_w: &mut writer::Encoder, id: def_id) {
 301     ebml_w.start_tag(tag_items_data_parent_item);
 302     let s = def_to_str(id);
 303     ebml_w.writer.write(s.as_bytes());
 304     ebml_w.end_tag();
 305 }
 306
 307 fn encode_enum_variant_info(ecx: &EncodeContext,
 308                             ebml_w: &mut writer::Encoder,
 309                             id: node_id,
 310                             variants: &[variant],
 311                             path: &[ast_map::path_elt],
 312                             index: @mut ~[entry<int>],
 313                             generics: &ast::Generics) {
 314     debug!("encode_enum_variant_info(id=%?)", id);
 315
 316     let mut disr_val = 0;
 317     let mut i = 0;
 318     let vi = ty::enum_variants(ecx.tcx,
 319                                ast::def_id { crate: local_crate, node: id });
 320     for variants.iter().advance |variant| {
 321         let def_id = local_def(variant.node.id);
 322         index.push(entry {val: variant.node.id, pos: ebml_w.writer.tell()});
 323         ebml_w.start_tag(tag_items_data_item);
 324         encode_def_id(ebml_w, def_id);
 325         encode_family(ebml_w, 'v');
 326         encode_name(ecx, ebml_w, variant.node.name);
 327         encode_parent_item(ebml_w, local_def(id));
 328         encode_visibility(ebml_w, variant.node.vis);
 329         match variant.node.kind {
 330             ast::tuple_variant_kind(ref args)
 331                     if args.len() > 0 && generics.ty_params.len() == 0 => {
 332                 encode_symbol(ecx, ebml_w, variant.node.id);
 333             }
 334             ast::tuple_variant_kind(_) | ast::struct_variant_kind(_) => {}
 335         }
 336         encode_discriminant(ecx, ebml_w, variant.node.id);
 337         if vi[i].disr_val != disr_val {
 338             encode_disr_val(ecx, ebml_w, vi[i].disr_val);
 339             disr_val = vi[i].disr_val;
 340         }
 341         encode_bounds_and_type(ebml_w, ecx,
 342                                &lookup_item_type(ecx.tcx, def_id));
 343         encode_path(ecx, ebml_w, path,
 344                     ast_map::path_name(variant.node.name));
 345         ebml_w.end_tag();
 346         disr_val += 1;
 347         i += 1;
 348     }
 349 }
 350
 351 fn encode_path(ecx: &EncodeContext,
 352                ebml_w: &mut writer::Encoder,
 353                path: &[ast_map::path_elt],
 354                name: ast_map::path_elt) {
 355     fn encode_path_elt(ecx: &EncodeContext,
 356                        ebml_w: &mut writer::Encoder,
 357                        elt: ast_map::path_elt) {
 358         let (tag, name) = match elt {
 359           ast_map::path_mod(name) => (tag_path_elt_mod, name),
 360           ast_map::path_name(name) => (tag_path_elt_name, name)
 361         };
 362
 363         ebml_w.wr_tagged_str(tag, ecx.tcx.sess.str_of(name));
 364     }
 365
 366     ebml_w.start_tag(tag_path);
 367     ebml_w.wr_tagged_u32(tag_path_len, (path.len() + 1) as u32);
 368     for path.iter().advance |pe| {
 369         encode_path_elt(ecx, ebml_w, *pe);
 370     }
 371     encode_path_elt(ecx, ebml_w, name);
 372     ebml_w.end_tag();
 373 }
 374
 375 fn encode_reexported_static_method(ecx: &EncodeContext,
 376                                    ebml_w: &mut writer::Encoder,
 377                                    exp: &middle::resolve::Export2,
 378                                    method_def_id: def_id,
 379                                    method_ident: ident) {
 380     debug!("(encode reexported static method) %s::%s",
 381             exp.name, ecx.tcx.sess.str_of(method_ident));
 382     ebml_w.start_tag(tag_items_data_item_reexport);
 383     ebml_w.start_tag(tag_items_data_item_reexport_def_id);
 384     ebml_w.wr_str(def_to_str(method_def_id));
 385     ebml_w.end_tag();
 386     ebml_w.start_tag(tag_items_data_item_reexport_name);
 387     ebml_w.wr_str(fmt!("%s::%s", exp.name, ecx.tcx.sess.str_of(method_ident)));
 388     ebml_w.end_tag();
 389     ebml_w.end_tag();
 390 }
 391
 392 fn encode_reexported_static_base_methods(ecx: &EncodeContext,
 393                                          ebml_w: &mut writer::Encoder,
 394                                          exp: &middle::resolve::Export2)
 395                                          -> bool {
 396     match ecx.tcx.inherent_impls.find(&exp.def_id) {
 397         Some(implementations) => {
 398             for implementations.iter().advance |&base_impl| {
 399                 for base_impl.methods.iter().advance |&m| {
 400                     if m.explicit_self == ast::sty_static {
 401                         encode_reexported_static_method(ecx, ebml_w, exp,
 402                                                         m.def_id, m.ident);
 403                     }
 404                 }
 405             }
 406
 407             true
 408         }
 409         None => { false }
 410     }
 411 }
 412
 413 fn encode_reexported_static_trait_methods(ecx: &EncodeContext,
 414                                           ebml_w: &mut writer::Encoder,
 415                                           exp: &middle::resolve::Export2)
 416                                           -> bool {
 417     match ecx.tcx.trait_methods_cache.find(&exp.def_id) {
 418         Some(methods) => {
 419             for methods.iter().advance |&m| {
 420                 if m.explicit_self == ast::sty_static {
 421                     encode_reexported_static_method(ecx, ebml_w, exp,
 422                                                     m.def_id, m.ident);
 423                 }
 424             }
 425
 426             true
 427         }
 428         None => { false }
 429     }
 430 }
 431
 432 fn encode_reexported_static_methods(ecx: &EncodeContext,
 433                                     ebml_w: &mut writer::Encoder,
 434                                     mod_path: &[ast_map::path_elt],
 435                                     exp: &middle::resolve::Export2) {
 436     match ecx.tcx.items.find(&exp.def_id.node) {
 437         Some(&ast_map::node_item(item, path)) => {
 438             let original_name = ecx.tcx.sess.str_of(item.ident);
 439
 440             //
 441             // We don't need to reexport static methods on items
 442             // declared in the same module as our `pub use ...` since
 443             // that's done when we encode the item itself.
 444             //
 445             // The only exception is when the reexport *changes* the
 446             // name e.g. `pub use Foo = self::Bar` -- we have
 447             // encoded metadata for static methods relative to Bar,
 448             // but not yet for Foo.
 449             //
 450             if mod_path != *path || exp.name != original_name {
 451                 if !encode_reexported_static_base_methods(ecx, ebml_w, exp) {
 452                     if encode_reexported_static_trait_methods(ecx, ebml_w, exp) {
 453                         debug!(fmt!("(encode reexported static methods) %s \
 454                                     [trait]",
 455                                     original_name));
 456                     }
 457                 }
 458                 else {
 459                     debug!(fmt!("(encode reexported static methods) %s [base]",
 460                                 original_name));
 461                 }
 462             }
 463         }
 464         _ => {}
 465     }
 466 }
 467
 468 /// Iterates through "auxiliary node IDs", which are node IDs that describe
 469 /// top-level items that are sub-items of the given item. Specifically:
 470 ///
 471 /// * For enums, iterates through the node IDs of the variants.
 472 ///
 473 /// * For newtype structs, iterates through the node ID of the constructor.
 474 fn each_auxiliary_node_id(item: @item, callback: &fn(node_id) -> bool)
 475                           -> bool {
 476     let mut continue = true;
 477     match item.node {
 478         item_enum(ref enum_def, _) => {
 479             for enum_def.variants.iter().advance |variant| {
 480                 continue = callback(variant.node.id);
 481                 if !continue {
 482                     break
 483                 }
 484             }
 485         }
 486         item_struct(struct_def, _) => {
 487             // If this is a newtype struct, return the constructor.
 488             match struct_def.ctor_id {
 489                 Some(ctor_id) if struct_def.fields.len() > 0 &&
 490                         struct_def.fields[0].node.kind ==
 491                         ast::unnamed_field => {
 492                     continue = callback(ctor_id);
 493                 }
 494                 _ => {}
 495             }
 496         }
 497         _ => {}
 498     }
 499
 500     continue
 501 }
 502
 503 fn encode_reexports(ecx: &EncodeContext,
 504                     ebml_w: &mut writer::Encoder,
 505                     id: node_id,
 506                     path: &[ast_map::path_elt]) {
 507     debug!("(encoding info for module) encoding reexports for %d", id);
 508     match ecx.reexports2.find(&id) {
 509         Some(ref exports) => {
 510             debug!("(encoding info for module) found reexports for %d", id);
 511             for exports.iter().advance |exp| {
 512                 debug!("(encoding info for module) reexport '%s' for %d",
 513                        exp.name, id);
 514                 ebml_w.start_tag(tag_items_data_item_reexport);
 515                 ebml_w.start_tag(tag_items_data_item_reexport_def_id);
 516                 ebml_w.wr_str(def_to_str(exp.def_id));
 517                 ebml_w.end_tag();
 518                 ebml_w.start_tag(tag_items_data_item_reexport_name);
 519                 ebml_w.wr_str(exp.name);
 520                 ebml_w.end_tag();
 521                 ebml_w.end_tag();
 522                 encode_reexported_static_methods(ecx, ebml_w, path, exp);
 523             }
 524         }
 525         None => {
 526             debug!("(encoding info for module) found no reexports for %d",
 527                    id);
 528         }
 529     }
 530 }
 531
 532 fn encode_info_for_mod(ecx: &EncodeContext,
 533                        ebml_w: &mut writer::Encoder,
 534                        md: &_mod,
 535                        id: node_id,
 536                        path: &[ast_map::path_elt],
 537                        name: ident,
 538                        vis: visibility) {
 539     ebml_w.start_tag(tag_items_data_item);
 540     encode_def_id(ebml_w, local_def(id));
 541     encode_family(ebml_w, 'm');
 542     encode_name(ecx, ebml_w, name);
 543     debug!("(encoding info for module) encoding info for module ID %d", id);
 544
 545     // Encode info about all the module children.
 546     for md.items.iter().advance |item| {
 547         ebml_w.start_tag(tag_mod_child);
 548         ebml_w.wr_str(def_to_str(local_def(item.id)));
 549         ebml_w.end_tag();
 550
 551         for each_auxiliary_node_id(*item) |auxiliary_node_id| {
 552             ebml_w.start_tag(tag_mod_child);
 553             ebml_w.wr_str(def_to_str(local_def(auxiliary_node_id)));
 554             ebml_w.end_tag();
 555         }
 556
 557         match item.node {
 558             item_impl(*) => {
 559                 let (ident, did) = (item.ident, item.id);
 560                 debug!("(encoding info for module) ... encoding impl %s \
 561                         (%?/%?)",
 562                         ecx.tcx.sess.str_of(ident),
 563                         did,
 564                         ast_map::node_id_to_str(ecx.tcx.items, did, token::get_ident_interner()));
 565
 566                 ebml_w.start_tag(tag_mod_impl);
 567                 ebml_w.wr_str(def_to_str(local_def(did)));
 568                 ebml_w.end_tag();
 569             }
 570             _ => {}
 571         }
 572     }
 573
 574     encode_path(ecx, ebml_w, path, ast_map::path_mod(name));
 575
 576     // Encode the reexports of this module, if this module is public.
 577     if vis == public {
 578         debug!("(encoding info for module) encoding reexports for %d", id);
 579         encode_reexports(ecx, ebml_w, id, path);
 580     }
 581
 582     ebml_w.end_tag();
 583 }
 584
 585 fn encode_struct_field_family(ebml_w: &mut writer::Encoder,
 586                               visibility: visibility) {
 587     encode_family(ebml_w, match visibility {
 588         public => 'g',
 589         private => 'j',
 590         inherited => 'N'
 591     });
 592 }
 593
 594 fn encode_visibility(ebml_w: &mut writer::Encoder, visibility: visibility) {
 595     ebml_w.start_tag(tag_items_data_item_visibility);
 596     let ch = match visibility {
 597         public => 'y',
 598         private => 'n',
 599         inherited => 'i',
 600     };
 601     ebml_w.wr_str(str::from_char(ch));
 602     ebml_w.end_tag();
 603 }
 604
 605 fn encode_explicit_self(ebml_w: &mut writer::Encoder, explicit_self: ast::explicit_self_) {
 606     ebml_w.start_tag(tag_item_trait_method_explicit_self);
 607
 608     // Encode the base self type.
 609     match explicit_self {
 610         sty_static => {
 611             ebml_w.writer.write(&[ 's' as u8 ]);
 612         }
 613         sty_value => {
 614             ebml_w.writer.write(&[ 'v' as u8 ]);
 615         }
 616         sty_region(_, m) => {
 617             // FIXME(#4846) encode custom lifetime
 618             ebml_w.writer.write(&[ '&' as u8 ]);
 619             encode_mutability(ebml_w, m);
 620         }
 621         sty_box(m) => {
 622             ebml_w.writer.write(&[ '@' as u8 ]);
 623             encode_mutability(ebml_w, m);
 624         }
 625         sty_uniq => {
 626             ebml_w.writer.write(&[ '~' as u8 ]);
 627         }
 628     }
 629
 630     ebml_w.end_tag();
 631
 632     fn encode_mutability(ebml_w: &writer::Encoder,
 633                          m: ast::mutability) {
 634         match m {
 635             m_imm => {
 636                 ebml_w.writer.write(&[ 'i' as u8 ]);
 637             }
 638             m_mutbl => {
 639                 ebml_w.writer.write(&[ 'm' as u8 ]);
 640             }
 641             m_const => {
 642                 ebml_w.writer.write(&[ 'c' as u8 ]);
 643             }
 644         }
 645     }
 646 }
 647
 648 fn encode_method_sort(ebml_w: &mut writer::Encoder, sort: char) {
 649     ebml_w.start_tag(tag_item_trait_method_sort);
 650     ebml_w.writer.write(&[ sort as u8 ]);
 651     ebml_w.end_tag();
 652 }
 653
 654 fn encode_provided_source(ebml_w: &mut writer::Encoder,
 655                           source_opt: Option<def_id>) {
 656     for source_opt.iter().advance |source| {
 657         ebml_w.start_tag(tag_item_method_provided_source);
 658         let s = def_to_str(*source);
 659         ebml_w.writer.write(s.as_bytes());
 660         ebml_w.end_tag();
 661     }
 662 }
 663
 664 /* Returns an index of items in this class */
 665 fn encode_info_for_struct(ecx: &EncodeContext,
 666                           ebml_w: &mut writer::Encoder,
 667                           path: &[ast_map::path_elt],
 668                           fields: &[@struct_field],
 669                           global_index: @mut ~[entry<int>])
 670                           -> ~[entry<int>] {
 671     /* Each class has its own index, since different classes
 672        may have fields with the same name */
 673     let mut index = ~[];
 674     let tcx = ecx.tcx;
 675      /* We encode both private and public fields -- need to include
 676         private fields to get the offsets right */
 677     for fields.iter().advance |field| {
 678         let (nm, vis) = match field.node.kind {
 679             named_field(nm, vis) => (nm, vis),
 680             unnamed_field => (special_idents::unnamed_field, inherited)
 681         };
 682
 683         let id = field.node.id;
 684         index.push(entry {val: id, pos: ebml_w.writer.tell()});
 685         global_index.push(entry {val: id, pos: ebml_w.writer.tell()});
 686         ebml_w.start_tag(tag_items_data_item);
 687         debug!("encode_info_for_struct: doing %s %d",
 688                tcx.sess.str_of(nm), id);
 689         encode_struct_field_family(ebml_w, vis);
 690         encode_name(ecx, ebml_w, nm);
 691         encode_path(ecx, ebml_w, path, ast_map::path_name(nm));
 692         encode_type(ecx, ebml_w, node_id_to_type(tcx, id));
 693         encode_def_id(ebml_w, local_def(id));
 694         ebml_w.end_tag();
 695     }
 696     index
 697 }
 698
 699 fn encode_info_for_struct_ctor(ecx: &EncodeContext,
 700                                ebml_w: &mut writer::Encoder,
 701                                path: &[ast_map::path_elt],
 702                                name: ast::ident,
 703                                ctor_id: node_id,
 704                                index: @mut ~[entry<int>]) {
 705     index.push(entry { val: ctor_id, pos: ebml_w.writer.tell() });
 706
 707     ebml_w.start_tag(tag_items_data_item);
 708     encode_def_id(ebml_w, local_def(ctor_id));
 709     encode_family(ebml_w, 'f');
 710     encode_name(ecx, ebml_w, name);
 711     encode_type(ecx, ebml_w, node_id_to_type(ecx.tcx, ctor_id));
 712     encode_path(ecx, ebml_w, path, ast_map::path_name(name));
 713
 714     if ecx.item_symbols.contains_key(&ctor_id) {
 715         encode_symbol(ecx, ebml_w, ctor_id);
 716     }
 717
 718     ebml_w.end_tag();
 719 }
 720
 721 fn encode_method_ty_fields(ecx: &EncodeContext,
 722                            ebml_w: &mut writer::Encoder,
 723                            method_ty: &ty::Method) {
 724     encode_def_id(ebml_w, method_ty.def_id);
 725     encode_name(ecx, ebml_w, method_ty.ident);
 726     encode_ty_type_param_defs(ebml_w, ecx,
 727                               method_ty.generics.type_param_defs,
 728                               tag_item_method_tps);
 729     encode_transformed_self_ty(ecx, ebml_w, method_ty.transformed_self_ty);
 730     encode_method_fty(ecx, ebml_w, &method_ty.fty);
 731     encode_visibility(ebml_w, method_ty.vis);
 732     encode_explicit_self(ebml_w, method_ty.explicit_self);
 733     let purity = method_ty.fty.purity;
 734     match method_ty.explicit_self {
 735         ast::sty_static => {
 736             encode_family(ebml_w, purity_static_method_family(purity));
 737         }
 738         _ => encode_family(ebml_w, purity_fn_family(purity))
 739     }
 740     encode_provided_source(ebml_w, method_ty.provided_source);
 741 }
 742
 743 fn encode_info_for_method(ecx: &EncodeContext,
 744                           ebml_w: &mut writer::Encoder,
 745                           m: &ty::Method,
 746                           impl_path: &[ast_map::path_elt],
 747                           is_default_impl: bool,
 748                           parent_id: node_id,
 749                           ast_method_opt: Option<@method>) {
 750
 751     debug!("encode_info_for_method: %? %s", m.def_id,
 752            ecx.tcx.sess.str_of(m.ident));
 753     ebml_w.start_tag(tag_items_data_item);
 754
 755     encode_method_ty_fields(ecx, ebml_w, m);
 756     encode_parent_item(ebml_w, local_def(parent_id));
 757
 758     // The type for methods gets encoded twice, which is unfortunate.
 759     let tpt = lookup_item_type(ecx.tcx, m.def_id);
 760     encode_bounds_and_type(ebml_w, ecx, &tpt);
 761
 762     encode_path(ecx, ebml_w, impl_path, ast_map::path_name(m.ident));
 763
 764     for ast_method_opt.iter().advance |ast_method| {
 765         let num_params = tpt.generics.type_param_defs.len();
 766         if num_params > 0u || is_default_impl
 767             || should_inline(ast_method.attrs) {
 768             (ecx.encode_inlined_item)(
 769                 ecx, ebml_w, impl_path,
 770                 ii_method(local_def(parent_id), false, *ast_method));
 771         } else {
 772             encode_symbol(ecx, ebml_w, m.def_id.node);
 773         }
 774     }
 775
 776     ebml_w.end_tag();
 777 }
 778
 779 fn purity_fn_family(p: purity) -> char {
 780     match p {
 781       unsafe_fn => 'u',
 782       impure_fn => 'f',
 783       extern_fn => 'e'
 784     }
 785 }
 786
 787 fn purity_static_method_family(p: purity) -> char {
 788     match p {
 789       unsafe_fn => 'U',
 790       impure_fn => 'F',
 791       _ => fail!("extern fn can't be static")
 792     }
 793 }
 794
 795
 796 fn should_inline(attrs: &[Attribute]) -> bool {
 797     use syntax::attr::*;
 798     match find_inline_attr(attrs) {
 799         InlineNone | InlineNever  => false,
 800         InlineHint | InlineAlways => true
 801     }
 802 }
 803
 804 fn encode_info_for_item(ecx: &EncodeContext,
 805                         ebml_w: &mut writer::Encoder,
 806                         item: @item,
 807                         index: @mut ~[entry<int>],
 808                         path: &[ast_map::path_elt]) {
 809     let tcx = ecx.tcx;
 810
 811     fn add_to_index_(item: @item, ebml_w: &writer::Encoder,
 812                      index: @mut ~[entry<int>]) {
 813         index.push(entry { val: item.id, pos: ebml_w.writer.tell() });
 814     }
 815     let add_to_index: &fn() = || add_to_index_(item, ebml_w, index);
 816
 817     debug!("encoding info for item at %s",
 818            ecx.tcx.sess.codemap.span_to_str(item.span));
 819
 820     let def_id = local_def(item.id);
 821     match item.node {
 822       item_static(_, m, _) => {
 823         add_to_index();
 824         ebml_w.start_tag(tag_items_data_item);
 825         encode_def_id(ebml_w, def_id);
 826         if m == ast::m_mutbl {
 827             encode_family(ebml_w, 'b');
 828         } else {
 829             encode_family(ebml_w, 'c');
 830         }
 831         encode_type(ecx, ebml_w, node_id_to_type(tcx, item.id));
 832         encode_symbol(ecx, ebml_w, item.id);
 833         encode_name(ecx, ebml_w, item.ident);
 834         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
 835         (ecx.encode_inlined_item)(ecx, ebml_w, path, ii_item(item));
 836         ebml_w.end_tag();
 837       }
 838       item_fn(_, purity, _, ref generics, _) => {
 839         add_to_index();
 840         ebml_w.start_tag(tag_items_data_item);
 841         encode_def_id(ebml_w, def_id);
 842         encode_family(ebml_w, purity_fn_family(purity));
 843         let tps_len = generics.ty_params.len();
 844         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
 845         encode_name(ecx, ebml_w, item.ident);
 846         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
 847         encode_attributes(ebml_w, item.attrs);
 848         if tps_len > 0u || should_inline(item.attrs) {
 849             (ecx.encode_inlined_item)(ecx, ebml_w, path, ii_item(item));
 850         } else {
 851             encode_symbol(ecx, ebml_w, item.id);
 852         }
 853         ebml_w.end_tag();
 854       }
 855       item_mod(ref m) => {
 856         add_to_index();
 857         encode_info_for_mod(ecx,
 858                             ebml_w,
 859                             m,
 860                             item.id,
 861                             path,
 862                             item.ident,
 863                             item.vis);
 864       }
 865       item_foreign_mod(ref fm) => {
 866         add_to_index();
 867         ebml_w.start_tag(tag_items_data_item);
 868         encode_def_id(ebml_w, def_id);
 869         encode_family(ebml_w, 'n');
 870         encode_name(ecx, ebml_w, item.ident);
 871         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
 872
 873         // Encode all the items in this module.
 874         for fm.items.iter().advance |foreign_item| {
 875             ebml_w.start_tag(tag_mod_child);
 876             ebml_w.wr_str(def_to_str(local_def(foreign_item.id)));
 877             ebml_w.end_tag();
 878         }
 879
 880         ebml_w.end_tag();
 881       }
 882       item_ty(*) => {
 883         add_to_index();
 884         ebml_w.start_tag(tag_items_data_item);
 885         encode_def_id(ebml_w, def_id);
 886         encode_family(ebml_w, 'y');
 887         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
 888         encode_name(ecx, ebml_w, item.ident);
 889         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
 890         encode_region_param(ecx, ebml_w, item);
 891         ebml_w.end_tag();
 892       }
 893       item_enum(ref enum_definition, ref generics) => {
 894         add_to_index();
 895
 896         ebml_w.start_tag(tag_items_data_item);
 897         encode_def_id(ebml_w, def_id);
 898         encode_family(ebml_w, 't');
 899         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
 900         encode_name(ecx, ebml_w, item.ident);
 901         for (*enum_definition).variants.iter().advance |v| {
 902             encode_variant_id(ebml_w, local_def(v.node.id));
 903         }
 904         (ecx.encode_inlined_item)(ecx, ebml_w, path, ii_item(item));
 905         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
 906         encode_region_param(ecx, ebml_w, item);
 907         ebml_w.end_tag();
 908
 909         encode_enum_variant_info(ecx,
 910                                  ebml_w,
 911                                  item.id,
 912                                  (*enum_definition).variants,
 913                                  path,
 914                                  index,
 915                                  generics);
 916       }
 917       item_struct(struct_def, _) => {
 918         /* First, encode the fields
 919            These come first because we need to write them to make
 920            the index, and the index needs to be in the item for the
 921            class itself */
 922         let idx = encode_info_for_struct(ecx, ebml_w, path,
 923                                          struct_def.fields, index);
 924
 925         /* Index the class*/
 926         add_to_index();
 927
 928         /* Now, make an item for the class itself */
 929         ebml_w.start_tag(tag_items_data_item);
 930         encode_def_id(ebml_w, def_id);
 931         encode_family(ebml_w, 'S');
 932         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
 933
 934         encode_name(ecx, ebml_w, item.ident);
 935         encode_attributes(ebml_w, item.attrs);
 936         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
 937         encode_region_param(ecx, ebml_w, item);
 938
 939         /* Encode def_ids for each field and method
 940          for methods, write all the stuff get_trait_method
 941         needs to know*/
 942         for struct_def.fields.iter().advance |f| {
 943             match f.node.kind {
 944                 named_field(ident, vis) => {
 945                    ebml_w.start_tag(tag_item_field);
 946                    encode_struct_field_family(ebml_w, vis);
 947                    encode_name(ecx, ebml_w, ident);
 948                    encode_def_id(ebml_w, local_def(f.node.id));
 949                    ebml_w.end_tag();
 950                 }
 951                 unnamed_field => {
 952                     ebml_w.start_tag(tag_item_unnamed_field);
 953                     encode_def_id(ebml_w, local_def(f.node.id));
 954                     ebml_w.end_tag();
 955                 }
 956             }
 957         }
 958
 959         /* Each class has its own index -- encode it */
 960         let bkts = create_index(idx);
 961         encode_index(ebml_w, bkts, write_int);
 962         ebml_w.end_tag();
 963
 964         // If this is a tuple- or enum-like struct, encode the type of the
 965         // constructor.
 966         if struct_def.fields.len() > 0 &&
 967                 struct_def.fields[0].node.kind == ast::unnamed_field {
 968             let ctor_id = match struct_def.ctor_id {
 969                 Some(ctor_id) => ctor_id,
 970                 None => ecx.tcx.sess.bug("struct def didn't have ctor id"),
 971             };
 972
 973             encode_info_for_struct_ctor(ecx,
 974                                         ebml_w,
 975                                         path,
 976                                         item.ident,
 977                                         ctor_id,
 978                                         index);
 979         }
 980       }
 981       item_impl(_, ref opt_trait, ref ty, ref ast_methods) => {
 982         // We need to encode information about the default methods we
 983         // have inherited, so we drive this based on the impl structure.
 984         let imp = tcx.impls.get(&def_id);
 985
 986         add_to_index();
 987         ebml_w.start_tag(tag_items_data_item);
 988         encode_def_id(ebml_w, def_id);
 989         encode_family(ebml_w, 'i');
 990         encode_region_param(ecx, ebml_w, item);
 991         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
 992         encode_name(ecx, ebml_w, item.ident);
 993         encode_attributes(ebml_w, item.attrs);
 994         match ty.node {
 995             ast::ty_path(ref path, ref bounds, _) if path.idents.len() == 1 => {
 996                 assert!(bounds.is_none());
 997                 encode_impl_type_basename(ecx, ebml_w,
 998                                           ast_util::path_to_ident(path));
 999             }
1000             _ => {}
1001         }
1002         for imp.methods.iter().advance |method| {
1003             ebml_w.start_tag(tag_item_impl_method);
1004             let s = def_to_str(method.def_id);
1005             ebml_w.writer.write(s.as_bytes());
1006             ebml_w.end_tag();
1007         }
1008         for opt_trait.iter().advance |ast_trait_ref| {
1009             let trait_ref = ty::node_id_to_trait_ref(
1010                 tcx, ast_trait_ref.ref_id);
1011             encode_trait_ref(ebml_w, ecx, trait_ref, tag_item_trait_ref);
1012         }
1013         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
1014         ebml_w.end_tag();
1015
1016         // >:-<
1017         let mut impl_path = vec::append(~[], path);
1018         impl_path.push(ast_map::path_name(item.ident));
1019
1020         // Iterate down the methods, emitting them. We rely on the
1021         // assumption that all of the actually implemented methods
1022         // appear first in the impl structure, in the same order they do
1023         // in the ast. This is a little sketchy.
1024         let num_implemented_methods = ast_methods.len();
1025         for imp.methods.iter().enumerate().advance |(i, m)| {
1026             let ast_method = if i < num_implemented_methods {
1027                 Some(ast_methods[i])
1028             } else { None };
1029
1030             index.push(entry {val: m.def_id.node, pos: ebml_w.writer.tell()});
1031             encode_info_for_method(ecx,
1032                                    ebml_w,
1033                                    *m,
1034                                    impl_path,
1035                                    false,
1036                                    item.id,
1037                                    ast_method)
1038         }
1039       }
1040       item_trait(_, ref super_traits, ref ms) => {
1041         add_to_index();
1042         ebml_w.start_tag(tag_items_data_item);
1043         encode_def_id(ebml_w, def_id);
1044         encode_family(ebml_w, 'I');
1045         encode_region_param(ecx, ebml_w, item);
1046         let trait_def = ty::lookup_trait_def(tcx, def_id);
1047         encode_ty_type_param_defs(ebml_w, ecx,
1048                                   trait_def.generics.type_param_defs,
1049                                   tag_items_data_item_ty_param_bounds);
1050         encode_trait_ref(ebml_w, ecx, trait_def.trait_ref, tag_item_trait_ref);
1051         encode_name(ecx, ebml_w, item.ident);
1052         encode_attributes(ebml_w, item.attrs);
1053         for ty::trait_method_def_ids(tcx, def_id).iter().advance |&method_def_id| {
1054             ebml_w.start_tag(tag_item_trait_method);
1055             encode_def_id(ebml_w, method_def_id);
1056             ebml_w.end_tag();
1057
1058             ebml_w.start_tag(tag_mod_child);
1059             ebml_w.wr_str(def_to_str(method_def_id));
1060             ebml_w.end_tag();
1061         }
1062         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
1063         for super_traits.iter().advance |ast_trait_ref| {
1064             let trait_ref = ty::node_id_to_trait_ref(ecx.tcx, ast_trait_ref.ref_id);
1065             encode_trait_ref(ebml_w, ecx, trait_ref, tag_item_super_trait_ref);
1066         }
1067         ebml_w.end_tag();
1068
1069         // Now output the method info for each method.
1070         let r = ty::trait_method_def_ids(tcx, def_id);
1071         for r.iter().enumerate().advance |(i, &method_def_id)| {
1072             assert_eq!(method_def_id.crate, ast::local_crate);
1073
1074             let method_ty = ty::method(tcx, method_def_id);
1075
1076             index.push(entry {val: method_def_id.node, pos: ebml_w.writer.tell()});
1077
1078             ebml_w.start_tag(tag_items_data_item);
1079
1080             encode_method_ty_fields(ecx, ebml_w, method_ty);
1081
1082             encode_parent_item(ebml_w, def_id);
1083
1084             let mut trait_path = vec::append(~[], path);
1085             trait_path.push(ast_map::path_name(item.ident));
1086             encode_path(ecx, ebml_w, trait_path, ast_map::path_name(method_ty.ident));
1087
1088             match method_ty.explicit_self {
1089                 sty_static => {
1090                     encode_family(ebml_w,
1091                                   purity_static_method_family(
1092                                       method_ty.fty.purity));
1093
1094                     let tpt = ty::lookup_item_type(tcx, method_def_id);
1095                     encode_bounds_and_type(ebml_w, ecx, &tpt);
1096                 }
1097
1098                 _ => {
1099                     encode_family(ebml_w,
1100                                   purity_fn_family(
1101                                       method_ty.fty.purity));
1102                 }
1103             }
1104
1105             match ms[i] {
1106                 required(_) => {
1107                     encode_method_sort(ebml_w, 'r');
1108                 }
1109
1110                 provided(m) => {
1111                     // If this is a static method, we've already encoded
1112                     // this.
1113                     if method_ty.explicit_self != sty_static {
1114                         // XXX: I feel like there is something funny going on.
1115                         let tpt = ty::lookup_item_type(tcx, method_def_id);
1116                         encode_bounds_and_type(ebml_w, ecx, &tpt);
1117                     }
1118                     encode_method_sort(ebml_w, 'p');
1119                     (ecx.encode_inlined_item)(
1120                         ecx, ebml_w, path,
1121                         ii_method(def_id, true, m));
1122                 }
1123             }
1124
1125             ebml_w.end_tag();
1126         }
1127       }
1128       item_mac(*) => fail!("item macros unimplemented")
1129     }
1130 }
1131
1132 fn encode_info_for_foreign_item(ecx: &EncodeContext,
1133                                 ebml_w: &mut writer::Encoder,
1134                                 nitem: @foreign_item,
1135                                 index: @mut ~[entry<int>],
1136                                 path: &ast_map::path,
1137                                 abi: AbiSet) {
1138     index.push(entry { val: nitem.id, pos: ebml_w.writer.tell() });
1139
1140     ebml_w.start_tag(tag_items_data_item);
1141     match nitem.node {
1142       foreign_item_fn(_, purity, _) => {
1143         encode_def_id(ebml_w, local_def(nitem.id));
1144         encode_family(ebml_w, purity_fn_family(purity));
1145         encode_bounds_and_type(ebml_w, ecx,
1146                                &lookup_item_type(ecx.tcx,local_def(nitem.id)));
1147         encode_name(ecx, ebml_w, nitem.ident);
1148         if abi.is_intrinsic() {
1149             (ecx.encode_inlined_item)(ecx, ebml_w, *path, ii_foreign(nitem));
1150         } else {
1151             encode_symbol(ecx, ebml_w, nitem.id);
1152         }
1153         encode_path(ecx, ebml_w, *path, ast_map::path_name(nitem.ident));
1154       }
1155       foreign_item_static(_, mutbl) => {
1156         encode_def_id(ebml_w, local_def(nitem.id));
1157         if mutbl {
1158             encode_family(ebml_w, 'b');
1159         } else {
1160             encode_family(ebml_w, 'c');
1161         }
1162         encode_type(ecx, ebml_w, node_id_to_type(ecx.tcx, nitem.id));
1163         encode_symbol(ecx, ebml_w, nitem.id);
1164         encode_name(ecx, ebml_w, nitem.ident);
1165         encode_path(ecx, ebml_w, *path, ast_map::path_name(nitem.ident));
1166       }
1167     }
1168     ebml_w.end_tag();
1169 }
1170
1171 fn encode_info_for_items(ecx: &EncodeContext,
1172                          ebml_w: &mut writer::Encoder,
1173                          crate: &Crate)
1174                          -> ~[entry<int>] {
1175     let index = @mut ~[];
1176     ebml_w.start_tag(tag_items_data);
1177     index.push(entry { val: crate_node_id, pos: ebml_w.writer.tell() });
1178     encode_info_for_mod(ecx,
1179                         ebml_w,
1180                         &crate.module,
1181                         crate_node_id,
1182                         [],
1183                         syntax::parse::token::special_idents::invalid,
1184                         public);
1185     let items = ecx.tcx.items;
1186
1187     // See comment in `encode_side_tables_for_ii` in astencode
1188     let ecx_ptr : *() = unsafe { cast::transmute(ecx) };
1189
1190     visit::visit_crate(crate, ((), visit::mk_vt(@visit::Visitor {
1191         visit_expr: |_e, (_cx, _v)| { },
1192         visit_item: {
1193             let ebml_w = (*ebml_w).clone();
1194             |i, (cx, v)| {
1195                 visit::visit_item(i, (cx, v));
1196                 match items.get_copy(&i.id) {
1197                     ast_map::node_item(_, pt) => {
1198                         let mut ebml_w = ebml_w.clone();
1199                         // See above
1200                         let ecx : &EncodeContext = unsafe { cast::transmute(ecx_ptr) };
1201                         encode_info_for_item(ecx, &mut ebml_w, i, index, *pt);
1202                     }
1203                     _ => fail!("bad item")
1204                 }
1205             }
1206         },
1207         visit_foreign_item: {
1208             let ebml_w = (*ebml_w).clone();
1209             |ni, (cx, v)| {
1210                 visit::visit_foreign_item(ni, (cx, v));
1211                 match items.get_copy(&ni.id) {
1212                     ast_map::node_foreign_item(_, abi, _, pt) => {
1213                         debug!("writing foreign item %s::%s",
1214                                ast_map::path_to_str(
1215                                 *pt,
1216                                 token::get_ident_interner()),
1217                                 token::ident_to_str(&ni.ident));
1218
1219                         let mut ebml_w = ebml_w.clone();
1220                         // See above
1221                         let ecx : &EncodeContext = unsafe { cast::transmute(ecx_ptr) };
1222                         encode_info_for_foreign_item(ecx,
1223                                                      &mut ebml_w,
1224                                                      ni,
1225                                                      index,
1226                                                      pt,
1227                                                      abi);
1228                     }
1229                     // case for separate item and foreign-item tables
1230                     _ => fail!("bad foreign item")
1231                 }
1232             }
1233         },
1234         ..*visit::default_visitor()
1235     })));
1236     ebml_w.end_tag();
1237     return /*bad*/(*index).clone();
1238 }
1239
1240
1241 // Path and definition ID indexing
1242
1243 fn create_index<T:Clone + Hash + IterBytes + 'static>(
1244                 index: ~[entry<T>])
1245                 -> ~[@~[entry<T>]] {
1246     let mut buckets: ~[@mut ~[entry<T>]] = ~[];
1247     for uint::range(0u, 256u) |_i| { buckets.push(@mut ~[]); };
1248     for index.iter().advance |elt| {
1249         let h = elt.val.hash() as uint;
1250         buckets[h % 256].push((*elt).clone());
1251     }
1252
1253     let mut buckets_frozen = ~[];
1254     for buckets.iter().advance |bucket| {
1255         buckets_frozen.push(@/*bad*/(**bucket).clone());
1256     }
1257     return buckets_frozen;
1258 }
1259
1260 fn encode_index<T:'static>(
1261                 ebml_w: &mut writer::Encoder,
1262                 buckets: ~[@~[entry<T>]],
1263                 write_fn: &fn(@io::Writer, &T)) {
1264     let writer = ebml_w.writer;
1265     ebml_w.start_tag(tag_index);
1266     let mut bucket_locs: ~[uint] = ~[];
1267     ebml_w.start_tag(tag_index_buckets);
1268     for buckets.iter().advance |bucket| {
1269         bucket_locs.push(ebml_w.writer.tell());
1270         ebml_w.start_tag(tag_index_buckets_bucket);
1271         for (**bucket).iter().advance |elt| {
1272             ebml_w.start_tag(tag_index_buckets_bucket_elt);
1273             assert!(elt.pos < 0xffff_ffff);
1274             writer.write_be_u32(elt.pos as u32);
1275             write_fn(writer, &elt.val);
1276             ebml_w.end_tag();
1277         }
1278         ebml_w.end_tag();
1279     }
1280     ebml_w.end_tag();
1281     ebml_w.start_tag(tag_index_table);
1282     for bucket_locs.iter().advance |pos| {
1283         assert!(*pos < 0xffff_ffff);
1284         writer.write_be_u32(*pos as u32);
1285     }
1286     ebml_w.end_tag();
1287     ebml_w.end_tag();
1288 }
1289
1290 fn write_str(writer: @io::Writer, s: ~str) {
1291     writer.write_str(s);
1292 }
1293
1294 fn write_int(writer: @io::Writer, &n: &int) {
1295     assert!(n < 0x7fff_ffff);
1296     writer.write_be_u32(n as u32);
1297 }
1298
1299 fn encode_meta_item(ebml_w: &mut writer::Encoder, mi: @MetaItem) {
1300     match mi.node {
1301       MetaWord(name) => {
1302         ebml_w.start_tag(tag_meta_item_word);
1303         ebml_w.start_tag(tag_meta_item_name);
1304         ebml_w.writer.write(name.as_bytes());
1305         ebml_w.end_tag();
1306         ebml_w.end_tag();
1307       }
1308       MetaNameValue(name, value) => {
1309         match value.node {
1310           lit_str(value) => {
1311             ebml_w.start_tag(tag_meta_item_name_value);
1312             ebml_w.start_tag(tag_meta_item_name);
1313             ebml_w.writer.write(name.as_bytes());
1314             ebml_w.end_tag();
1315             ebml_w.start_tag(tag_meta_item_value);
1316             ebml_w.writer.write(value.as_bytes());
1317             ebml_w.end_tag();
1318             ebml_w.end_tag();
1319           }
1320           _ => {/* FIXME (#623): encode other variants */ }
1321         }
1322       }
1323       MetaList(name, ref items) => {
1324         ebml_w.start_tag(tag_meta_item_list);
1325         ebml_w.start_tag(tag_meta_item_name);
1326         ebml_w.writer.write(name.as_bytes());
1327         ebml_w.end_tag();
1328         for items.iter().advance |inner_item| {
1329             encode_meta_item(ebml_w, *inner_item);
1330         }
1331         ebml_w.end_tag();
1332       }
1333     }
1334 }
1335
1336 fn encode_attributes(ebml_w: &mut writer::Encoder, attrs: &[Attribute]) {
1337     ebml_w.start_tag(tag_attributes);
1338     for attrs.iter().advance |attr| {
1339         ebml_w.start_tag(tag_attribute);
1340         encode_meta_item(ebml_w, attr.node.value);
1341         ebml_w.end_tag();
1342     }
1343     ebml_w.end_tag();
1344 }
1345
1346 // So there's a special crate attribute called 'link' which defines the
1347 // metadata that Rust cares about for linking crates. This attribute requires
1348 // 'name' and 'vers' items, so if the user didn't provide them we will throw
1349 // them in anyway with default values.
1350 fn synthesize_crate_attrs(ecx: &EncodeContext,
1351                           crate: &Crate) -> ~[Attribute] {
1352
1353     fn synthesize_link_attr(ecx: &EncodeContext, items: ~[@MetaItem]) ->
1354        Attribute {
1355
1356         assert!(!ecx.link_meta.name.is_empty());
1357         assert!(!ecx.link_meta.vers.is_empty());
1358
1359         let name_item =
1360             attr::mk_name_value_item_str(@"name",
1361                                          ecx.link_meta.name);
1362         let vers_item =
1363             attr::mk_name_value_item_str(@"vers",
1364                                          ecx.link_meta.vers);
1365
1366         let mut meta_items = ~[name_item, vers_item];
1367
1368         for items.iter()
1369             .filter(|mi| "name" != mi.name() && "vers" != mi.name())
1370             .advance |&mi| {
1371             meta_items.push(mi);
1372         }
1373         let link_item = attr::mk_list_item(@"link", meta_items);
1374
1375         return attr::mk_attr(link_item);
1376     }
1377
1378     let mut attrs = ~[];
1379     let mut found_link_attr = false;
1380     for crate.attrs.iter().advance |attr| {
1381         attrs.push(
1382             if "link" != attr.name()  {
1383                 *attr
1384             } else {
1385                 match attr.meta_item_list() {
1386                   Some(l) => {
1387                     found_link_attr = true;;
1388                     synthesize_link_attr(ecx, l.to_owned())
1389                   }
1390                   _ => *attr
1391                 }
1392             });
1393     }
1394
1395     if !found_link_attr { attrs.push(synthesize_link_attr(ecx, ~[])); }
1396
1397     return attrs;
1398 }
1399
1400 fn encode_crate_deps(ecx: &EncodeContext,
1401                      ebml_w: &mut writer::Encoder,
1402                      cstore: &cstore::CStore) {
1403     fn get_ordered_deps(ecx: &EncodeContext, cstore: &cstore::CStore)
1404                      -> ~[decoder::crate_dep] {
1405         type numdep = decoder::crate_dep;
1406
1407         // Pull the cnums and name,vers,hash out of cstore
1408         let mut deps = ~[];
1409         do cstore::iter_crate_data(cstore) |key, val| {
1410             let dep = decoder::crate_dep {cnum: key,
1411                        name: ecx.tcx.sess.ident_of(val.name),
1412                        vers: decoder::get_crate_vers(val.data),
1413                        hash: decoder::get_crate_hash(val.data)};
1414             deps.push(dep);
1415         };
1416
1417         // Sort by cnum
1418         extra::sort::quick_sort(deps, |kv1, kv2| kv1.cnum <= kv2.cnum);
1419
1420         // Sanity-check the crate numbers
1421         let mut expected_cnum = 1;
1422         for deps.iter().advance |n| {
1423             assert_eq!(n.cnum, expected_cnum);
1424             expected_cnum += 1;
1425         }
1426
1427         deps
1428     }
1429
1430     // We're just going to write a list of crate 'name-hash-version's, with
1431     // the assumption that they are numbered 1 to n.
1432     // FIXME (#2166): This is not nearly enough to support correct versioning
1433     // but is enough to get transitive crate dependencies working.
1434     ebml_w.start_tag(tag_crate_deps);
1435     let r = get_ordered_deps(ecx, cstore);
1436     for r.iter().advance |dep| {
1437         encode_crate_dep(ecx, ebml_w, *dep);
1438     }
1439     ebml_w.end_tag();
1440 }
1441
1442 fn encode_lang_items(ecx: &EncodeContext, ebml_w: &mut writer::Encoder) {
1443     ebml_w.start_tag(tag_lang_items);
1444
1445     for ecx.tcx.lang_items.each_item |def_id, i| {
1446         if def_id.crate != local_crate {
1447             loop;
1448         }
1449
1450         ebml_w.start_tag(tag_lang_items_item);
1451
1452         ebml_w.start_tag(tag_lang_items_item_id);
1453         ebml_w.writer.write_be_u32(i as u32);
1454         ebml_w.end_tag();   // tag_lang_items_item_id
1455
1456         ebml_w.start_tag(tag_lang_items_item_node_id);
1457         ebml_w.writer.write_be_u32(def_id.node as u32);
1458         ebml_w.end_tag();   // tag_lang_items_item_node_id
1459
1460         ebml_w.end_tag();   // tag_lang_items_item
1461     }
1462
1463     ebml_w.end_tag();   // tag_lang_items
1464 }
1465
1466 fn encode_link_args(ecx: &EncodeContext, ebml_w: &mut writer::Encoder) {
1467     ebml_w.start_tag(tag_link_args);
1468
1469     let link_args = cstore::get_used_link_args(ecx.cstore);
1470     for link_args.iter().advance |link_arg| {
1471         ebml_w.start_tag(tag_link_args_arg);
1472         ebml_w.writer.write_str(link_arg.to_str());
1473         ebml_w.end_tag();
1474     }
1475
1476     ebml_w.end_tag();
1477 }
1478
1479 fn encode_misc_info(ecx: &EncodeContext,
1480                     crate: &Crate,
1481                     ebml_w: &mut writer::Encoder) {
1482     ebml_w.start_tag(tag_misc_info);
1483     ebml_w.start_tag(tag_misc_info_crate_items);
1484     for crate.module.items.iter().advance |&item| {
1485         ebml_w.start_tag(tag_mod_child);
1486         ebml_w.wr_str(def_to_str(local_def(item.id)));
1487         ebml_w.end_tag();
1488
1489         for each_auxiliary_node_id(item) |auxiliary_node_id| {
1490             ebml_w.start_tag(tag_mod_child);
1491             ebml_w.wr_str(def_to_str(local_def(auxiliary_node_id)));
1492             ebml_w.end_tag();
1493         }
1494     }
1495
1496     // Encode reexports for the root module.
1497     encode_reexports(ecx, ebml_w, 0, []);
1498
1499     ebml_w.end_tag();
1500     ebml_w.end_tag();
1501 }
1502
1503 fn encode_crate_dep(ecx: &EncodeContext,
1504                     ebml_w: &mut writer::Encoder,
1505                     dep: decoder::crate_dep) {
1506     ebml_w.start_tag(tag_crate_dep);
1507     ebml_w.start_tag(tag_crate_dep_name);
1508     let s = ecx.tcx.sess.str_of(dep.name);
1509     ebml_w.writer.write(s.as_bytes());
1510     ebml_w.end_tag();
1511     ebml_w.start_tag(tag_crate_dep_vers);
1512     ebml_w.writer.write(dep.vers.as_bytes());
1513     ebml_w.end_tag();
1514     ebml_w.start_tag(tag_crate_dep_hash);
1515     ebml_w.writer.write(dep.hash.as_bytes());
1516     ebml_w.end_tag();
1517     ebml_w.end_tag();
1518 }
1519
1520 fn encode_hash(ebml_w: &mut writer::Encoder, hash: &str) {
1521     ebml_w.start_tag(tag_crate_hash);
1522     ebml_w.writer.write(hash.as_bytes());
1523     ebml_w.end_tag();
1524 }
1525
1526 // NB: Increment this as you change the metadata encoding version.
1527 pub static metadata_encoding_version : &'static [u8] =
1528     &[0x72, //'r' as u8,
1529       0x75, //'u' as u8,
1530       0x73, //'s' as u8,
1531       0x74, //'t' as u8,
1532       0, 0, 0, 1 ];
1533
1534 pub fn encode_metadata(parms: EncodeParams, crate: &Crate) -> ~[u8] {
1535     let wr = @io::BytesWriter::new();
1536     let stats = Stats {
1537         inline_bytes: 0,
1538         attr_bytes: 0,
1539         dep_bytes: 0,
1540         lang_item_bytes: 0,
1541         link_args_bytes: 0,
1542         misc_bytes: 0,
1543         item_bytes: 0,
1544         index_bytes: 0,
1545         zero_bytes: 0,
1546         total_bytes: 0,
1547         n_inlines: 0
1548     };
1549     let EncodeParams {
1550         item_symbols,
1551         diag,
1552         tcx,
1553         reexports2,
1554         discrim_symbols,
1555         cstore,
1556         encode_inlined_item,
1557         link_meta,
1558         reachable,
1559         _
1560     } = parms;
1561     let type_abbrevs = @mut HashMap::new();
1562     let stats = @mut stats;
1563     let ecx = EncodeContext {
1564         diag: diag,
1565         tcx: tcx,
1566         stats: stats,
1567         reexports2: reexports2,
1568         item_symbols: item_symbols,
1569         discrim_symbols: discrim_symbols,
1570         link_meta: link_meta,
1571         cstore: cstore,
1572         encode_inlined_item: encode_inlined_item,
1573         type_abbrevs: type_abbrevs,
1574         reachable: reachable,
1575      };
1576
1577     let mut ebml_w = writer::Encoder(wr as @io::Writer);
1578
1579     encode_hash(&mut ebml_w, ecx.link_meta.extras_hash);
1580
1581     let mut i = *wr.pos;
1582     let crate_attrs = synthesize_crate_attrs(&ecx, crate);
1583     encode_attributes(&mut ebml_w, crate_attrs);
1584     ecx.stats.attr_bytes = *wr.pos - i;
1585
1586     i = *wr.pos;
1587     encode_crate_deps(&ecx, &mut ebml_w, ecx.cstore);
1588     ecx.stats.dep_bytes = *wr.pos - i;
1589
1590     // Encode the language items.
1591     i = *wr.pos;
1592     encode_lang_items(&ecx, &mut ebml_w);
1593     ecx.stats.lang_item_bytes = *wr.pos - i;
1594
1595     // Encode the link args.
1596     i = *wr.pos;
1597     encode_link_args(&ecx, &mut ebml_w);
1598     ecx.stats.link_args_bytes = *wr.pos - i;
1599
1600     // Encode miscellaneous info.
1601     i = *wr.pos;
1602     encode_misc_info(&ecx, crate, &mut ebml_w);
1603     ecx.stats.misc_bytes = *wr.pos - i;
1604
1605     // Encode and index the items.
1606     ebml_w.start_tag(tag_items);
1607     i = *wr.pos;
1608     let items_index = encode_info_for_items(&ecx, &mut ebml_w, crate);
1609     ecx.stats.item_bytes = *wr.pos - i;
1610
1611     i = *wr.pos;
1612     let items_buckets = create_index(items_index);
1613     encode_index(&mut ebml_w, items_buckets, write_int);
1614     ecx.stats.index_bytes = *wr.pos - i;
1615     ebml_w.end_tag();
1616
1617     ecx.stats.total_bytes = *wr.pos;
1618
1619     if (tcx.sess.meta_stats()) {
1620         for wr.bytes.iter().advance |e| {
1621             if *e == 0 {
1622                 ecx.stats.zero_bytes += 1;
1623             }
1624         }
1625
1626         io::println("metadata stats:");
1627         printfln!("    inline bytes: %u", ecx.stats.inline_bytes);
1628         printfln!(" attribute bytes: %u", ecx.stats.attr_bytes);
1629         printfln!("       dep bytes: %u", ecx.stats.dep_bytes);
1630         printfln!(" lang item bytes: %u", ecx.stats.lang_item_bytes);
1631         printfln!(" link args bytes: %u", ecx.stats.link_args_bytes);
1632         printfln!("      misc bytes: %u", ecx.stats.misc_bytes);
1633         printfln!("      item bytes: %u", ecx.stats.item_bytes);
1634         printfln!("     index bytes: %u", ecx.stats.index_bytes);
1635         printfln!("      zero bytes: %u", ecx.stats.zero_bytes);
1636         printfln!("     total bytes: %u", ecx.stats.total_bytes);
1637     }
1638
1639     // Pad this, since something (LLVM, presumably) is cutting off the
1640     // remaining % 4 bytes.
1641     wr.write(&[0u8, 0u8, 0u8, 0u8]);
1642
1643     let writer_bytes: &mut ~[u8] = wr.bytes;
1644
1645     metadata_encoding_version.to_owned() +
1646         flate::deflate_bytes(*writer_bytes)
1647 }
1648
1649 // Get the encoded string for a type
1650 pub fn encoded_ty(tcx: ty::ctxt, t: ty::t) -> ~str {
1651     let cx = @tyencode::ctxt {
1652         diag: tcx.diag,
1653         ds: def_to_str,
1654         tcx: tcx,
1655         abbrevs: tyencode::ac_no_abbrevs};
1656     do io::with_str_writer |wr| {
1657         tyencode::enc_ty(wr, cx, t);
1658     }
1659 }