src/librustc/metadata/encoder.rs

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