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