src/librbml/lib.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 //! Really Bad Markup Language (rbml) is an internal serialization format of rustc.
  12 //! This is not intended to be used by users.
  13 //!
  14 //! Originally based on the Extensible Binary Markup Language
  15 //! (ebml; http://www.matroska.org/technical/specs/rfc/index.html),
  16 //! it is now a separate format tuned for the rust object metadata.
  17 //!
  18 //! # Encoding
  19 //!
  20 //! RBML document consists of the tag, length and data.
  21 //! The encoded data can contain multiple RBML documents concatenated.
  22 //!
  23 //! **Tags** are a hint for the following data.
  24 //! Tags are a number from 0x000 to 0xfff, where 0xf0 through 0xff is reserved.
  25 //! Tags less than 0xf0 are encoded in one literal byte.
  26 //! Tags greater than 0xff are encoded in two big-endian bytes,
  27 //! where the tag number is ORed with 0xf000. (E.g. tag 0x123 = `f1 23`)
  28 //!
  29 //! **Lengths** encode the length of the following data.
  30 //! It is a variable-length unsigned int, and one of the following forms:
  31 //!
  32 //! - `80` through `fe` for lengths up to 0x7e;
  33 //! - `40 ff` through `7f ff` for lengths up to 0x3fff;
  34 //! - `20 40 00` through `3f ff ff` for lengths up to 0x1fffff;
  35 //! - `10 20 00 00` through `1f ff ff ff` for lengths up to 0xfffffff.
  36 //!
  37 //! The "overlong" form is allowed so that the length can be encoded
  38 //! without the prior knowledge of the encoded data.
  39 //! For example, the length 0 can be represented either by `80`, `40 00`,
  40 //! `20 00 00` or `10 00 00 00`.
  41 //! The encoder tries to minimize the length if possible.
  42 //! Also, some predefined tags listed below are so commonly used that
  43 //! their lengths are omitted ("implicit length").
  44 //!
  45 //! **Data** can be either binary bytes or zero or more nested RBML documents.
  46 //! Nested documents cannot overflow, and should be entirely contained
  47 //! within a parent document.
  48 //!
  49 //! # Predefined Tags
  50 //!
  51 //! Most RBML tags are defined by the application.
  52 //! (For the rust object metadata, see also `rustc::metadata::common`.)
  53 //! RBML itself does define a set of predefined tags however,
  54 //! intended for the auto-serialization implementation.
  55 //!
  56 //! Predefined tags with an implicit length:
  57 //!
  58 //! - `U8`  (`00`): 1-byte unsigned integer.
  59 //! - `U16` (`01`): 2-byte big endian unsigned integer.
  60 //! - `U32` (`02`): 4-byte big endian unsigned integer.
  61 //! - `U64` (`03`): 8-byte big endian unsigned integer.
  62 //!   Any of `U*` tags can be used to encode primitive unsigned integer types,
  63 //!   as long as it is no greater than the actual size.
  64 //!   For example, `u8` can only be represented via the `U8` tag.
  65 //!
  66 //! - `I8`  (`04`): 1-byte signed integer.
  67 //! - `I16` (`05`): 2-byte big endian signed integer.
  68 //! - `I32` (`06`): 4-byte big endian signed integer.
  69 //! - `I64` (`07`): 8-byte big endian signed integer.
  70 //!   Similar to `U*` tags. Always uses two's complement encoding.
  71 //!
  72 //! - `Bool` (`08`): 1-byte boolean value, `00` for false and `01` for true.
  73 //!
  74 //! - `Char` (`09`): 4-byte big endian Unicode scalar value.
  75 //!   Surrogate pairs or out-of-bound values are invalid.
  76 //!
  77 //! - `F32` (`0a`): 4-byte big endian unsigned integer representing
  78 //!   IEEE 754 binary32 floating-point format.
  79 //! - `F64` (`0b`): 8-byte big endian unsigned integer representing
  80 //!   IEEE 754 binary64 floating-point format.
  81 //!
  82 //! - `Sub8`  (`0c`): 1-byte unsigned integer for supplementary information.
  83 //! - `Sub32` (`0d`): 4-byte unsigned integer for supplementary information.
  84 //!   Those two tags normally occur as the first subdocument of certain tags,
  85 //!   namely `Enum`, `Vec` and `Map`, to provide a variant or size information.
  86 //!   They can be used interchangably.
  87 //!
  88 //! Predefined tags with an explicit length:
  89 //!
  90 //! - `Str` (`10`): A UTF-8-encoded string.
  91 //!
  92 //! - `Enum` (`11`): An enum.
  93 //!   The first subdocument should be `Sub*` tags with a variant ID.
  94 //!   Subsequent subdocuments, if any, encode variant arguments.
  95 //!
  96 //! - `Vec` (`12`): A vector (sequence).
  97 //! - `VecElt` (`13`): A vector element.
  98 //!   The first subdocument should be `Sub*` tags with the number of elements.
  99 //!   Subsequent subdocuments should be `VecElt` tag per each element.
 100 //!
 101 //! - `Map` (`14`): A map (associated array).
 102 //! - `MapKey` (`15`): A key part of the map entry.
 103 //! - `MapVal` (`16`): A value part of the map entry.
 104 //!   The first subdocument should be `Sub*` tags with the number of entries.
 105 //!   Subsequent subdocuments should be an alternating sequence of
 106 //!   `MapKey` and `MapVal` tags per each entry.
 107 //!
 108 //! - `Opaque` (`17`): An opaque, custom-format tag.
 109 //!   Used to wrap ordinary custom tags or data in the auto-serialized context.
 110 //!   Rustc typically uses this to encode type informations.
 111 //!
 112 //! First 0x20 tags are reserved by RBML; custom tags start at 0x20.
 113
 114 // Do not remove on snapshot creation. Needed for bootstrap. (Issue #22364)
 115 #![cfg_attr(stage0, feature(custom_attribute))]
 116 #![crate_name = "rbml"]
 117 #![unstable(feature = "rustc_private")]
 118 #![staged_api]
 119 #![crate_type = "rlib"]
 120 #![crate_type = "dylib"]
 121 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
 122        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
 123        html_root_url = "http://doc.rust-lang.org/nightly/",
 124        html_playground_url = "http://play.rust-lang.org/")]
 125
 126 #![feature(collections)]
 127 #![feature(core)]
 128 #![feature(int_uint)]
 129 #![feature(old_io)]
 130 #![feature(rustc_private)]
 131 #![feature(staged_api)]
 132
 133 #![cfg_attr(test, feature(test))]
 134
 135 extern crate serialize;
 136 #[macro_use] extern crate log;
 137
 138 #[cfg(test)] extern crate test;
 139
 140 pub use self::EbmlEncoderTag::*;
 141 pub use self::Error::*;
 142
 143 use std::str;
 144 use std::fmt;
 145
 146 pub mod io;
 147
 148 /// Common data structures
 149 #[derive(Clone, Copy)]
 150 pub struct Doc<'a> {
 151     pub data: &'a [u8],
 152     pub start: uint,
 153     pub end: uint,
 154 }
 155
 156 impl<'doc> Doc<'doc> {
 157     pub fn new(data: &'doc [u8]) -> Doc<'doc> {
 158         Doc { data: data, start: 0, end: data.len() }
 159     }
 160
 161     pub fn get<'a>(&'a self, tag: uint) -> Doc<'a> {
 162         reader::get_doc(*self, tag)
 163     }
 164
 165     pub fn is_empty(&self) -> bool {
 166         self.start == self.end
 167     }
 168
 169     pub fn as_str_slice<'a>(&'a self) -> &'a str {
 170         str::from_utf8(&self.data[self.start..self.end]).unwrap()
 171     }
 172
 173     pub fn as_str(&self) -> String {
 174         self.as_str_slice().to_string()
 175     }
 176 }
 177
 178 pub struct TaggedDoc<'a> {
 179     tag: uint,
 180     pub doc: Doc<'a>,
 181 }
 182
 183 #[derive(Copy, Debug)]
 184 pub enum EbmlEncoderTag {
 185     // tags 00..1f are reserved for auto-serialization.
 186     // first NUM_IMPLICIT_TAGS tags are implicitly sized and lengths are not encoded.
 187
 188     EsU8       = 0x00, // + 1 byte
 189     EsU16      = 0x01, // + 2 bytes
 190     EsU32      = 0x02, // + 4 bytes
 191     EsU64      = 0x03, // + 8 bytes
 192     EsI8       = 0x04, // + 1 byte
 193     EsI16      = 0x05, // + 2 bytes
 194     EsI32      = 0x06, // + 4 bytes
 195     EsI64      = 0x07, // + 8 bytes
 196     EsBool     = 0x08, // + 1 byte
 197     EsChar     = 0x09, // + 4 bytes
 198     EsF32      = 0x0a, // + 4 bytes
 199     EsF64      = 0x0b, // + 8 bytes
 200     EsSub8     = 0x0c, // + 1 byte
 201     EsSub32    = 0x0d, // + 4 bytes
 202     // 0x0e and 0x0f are reserved
 203
 204     EsStr      = 0x10,
 205     EsEnum     = 0x11, // encodes the variant id as the first EsSub*
 206     EsVec      = 0x12, // encodes the # of elements as the first EsSub*
 207     EsVecElt   = 0x13,
 208     EsMap      = 0x14, // encodes the # of pairs as the first EsSub*
 209     EsMapKey   = 0x15,
 210     EsMapVal   = 0x16,
 211     EsOpaque   = 0x17,
 212 }
 213
 214 const NUM_TAGS: uint = 0x1000;
 215 const NUM_IMPLICIT_TAGS: uint = 0x0e;
 216
 217 static TAG_IMPLICIT_LEN: [i8; NUM_IMPLICIT_TAGS] = [
 218     1, 2, 4, 8, // EsU*
 219     1, 2, 4, 8, // ESI*
 220     1, // EsBool
 221     4, // EsChar
 222     4, 8, // EsF*
 223     1, 4, // EsSub*
 224 ];
 225
 226 #[derive(Debug)]
 227 pub enum Error {
 228     IntTooBig(uint),
 229     InvalidTag(uint),
 230     Expected(String),
 231     IoError(std::old_io::IoError),
 232     ApplicationError(String)
 233 }
 234
 235 impl fmt::Display for Error {
 236     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 237         // FIXME: this should be a more useful display form
 238         fmt::Debug::fmt(self, f)
 239     }
 240 }
 241 // --------------------------------------
 242
 243 pub mod reader {
 244     use std::char;
 245
 246     use std::isize;
 247     use std::mem::transmute;
 248     use std::num::Int;
 249     use std::slice::bytes;
 250
 251     use serialize;
 252
 253     use super::{ ApplicationError, EsVec, EsMap, EsEnum, EsSub8, EsSub32,
 254         EsVecElt, EsMapKey, EsU64, EsU32, EsU16, EsU8, EsI64,
 255         EsI32, EsI16, EsI8, EsBool, EsF64, EsF32, EsChar, EsStr, EsMapVal,
 256         EsOpaque, EbmlEncoderTag, Doc, TaggedDoc,
 257         Error, IntTooBig, InvalidTag, Expected, NUM_IMPLICIT_TAGS, TAG_IMPLICIT_LEN };
 258
 259     pub type DecodeResult<T> = Result<T, Error>;
 260     // rbml reading
 261
 262     macro_rules! try_or {
 263         ($e:expr, $r:expr) => (
 264             match $e {
 265                 Ok(e) => e,
 266                 Err(e) => {
 267                     debug!("ignored error: {:?}", e);
 268                     return $r
 269                 }
 270             }
 271         )
 272     }
 273
 274     #[derive(Copy)]
 275     pub struct Res {
 276         pub val: uint,
 277         pub next: uint
 278     }
 279
 280     pub fn tag_at(data: &[u8], start: uint) -> DecodeResult<Res> {
 281         let v = data[start] as uint;
 282         if v < 0xf0 {
 283             Ok(Res { val: v, next: start + 1 })
 284         } else if v > 0xf0 {
 285             Ok(Res { val: ((v & 0xf) << 8) | data[start + 1] as uint, next: start + 2 })
 286         } else {
 287             // every tag starting with byte 0xf0 is an overlong form, which is prohibited.
 288             Err(InvalidTag(v))
 289         }
 290     }
 291
 292     #[inline(never)]
 293     fn vuint_at_slow(data: &[u8], start: uint) -> DecodeResult<Res> {
 294         let a = data[start];
 295         if a & 0x80 != 0 {
 296             return Ok(Res {val: (a & 0x7f) as uint, next: start + 1});
 297         }
 298         if a & 0x40 != 0 {
 299             return Ok(Res {val: ((a & 0x3f) as uint) << 8 |
 300                         (data[start + 1] as uint),
 301                     next: start + 2});
 302         }
 303         if a & 0x20 != 0 {
 304             return Ok(Res {val: ((a & 0x1f) as uint) << 16 |
 305                         (data[start + 1] as uint) << 8 |
 306                         (data[start + 2] as uint),
 307                     next: start + 3});
 308         }
 309         if a & 0x10 != 0 {
 310             return Ok(Res {val: ((a & 0x0f) as uint) << 24 |
 311                         (data[start + 1] as uint) << 16 |
 312                         (data[start + 2] as uint) << 8 |
 313                         (data[start + 3] as uint),
 314                     next: start + 4});
 315         }
 316         Err(IntTooBig(a as uint))
 317     }
 318
 319     pub fn vuint_at(data: &[u8], start: uint) -> DecodeResult<Res> {
 320         if data.len() - start < 4 {
 321             return vuint_at_slow(data, start);
 322         }
 323
 324         // Lookup table for parsing EBML Element IDs as per
 325         // http://ebml.sourceforge.net/specs/ The Element IDs are parsed by
 326         // reading a big endian u32 positioned at data[start].  Using the four
 327         // most significant bits of the u32 we lookup in the table below how
 328         // the element ID should be derived from it.
 329         //
 330         // The table stores tuples (shift, mask) where shift is the number the
 331         // u32 should be right shifted with and mask is the value the right
 332         // shifted value should be masked with.  If for example the most
 333         // significant bit is set this means it's a class A ID and the u32
 334         // should be right shifted with 24 and masked with 0x7f. Therefore we
 335         // store (24, 0x7f) at index 0x8 - 0xF (four bit numbers where the most
 336         // significant bit is set).
 337         //
 338         // By storing the number of shifts and masks in a table instead of
 339         // checking in order if the most significant bit is set, the second
 340         // most significant bit is set etc. we can replace up to three
 341         // "and+branch" with a single table lookup which gives us a measured
 342         // speedup of around 2x on x86_64.
 343         static SHIFT_MASK_TABLE: [(uint, u32); 16] = [
 344             (0, 0x0), (0, 0x0fffffff),
 345             (8, 0x1fffff), (8, 0x1fffff),
 346             (16, 0x3fff), (16, 0x3fff), (16, 0x3fff), (16, 0x3fff),
 347             (24, 0x7f), (24, 0x7f), (24, 0x7f), (24, 0x7f),
 348             (24, 0x7f), (24, 0x7f), (24, 0x7f), (24, 0x7f)
 349         ];
 350
 351         unsafe {
 352             let ptr = data.as_ptr().offset(start as int) as *const u32;
 353             let val = Int::from_be(*ptr);
 354
 355             let i = (val >> 28) as uint;
 356             let (shift, mask) = SHIFT_MASK_TABLE[i];
 357             Ok(Res {
 358                 val: ((val >> shift) & mask) as uint,
 359                 next: start + (((32 - shift) >> 3) as uint)
 360             })
 361         }
 362     }
 363
 364     pub fn tag_len_at(data: &[u8], tag: Res) -> DecodeResult<Res> {
 365         if tag.val < NUM_IMPLICIT_TAGS && TAG_IMPLICIT_LEN[tag.val] >= 0 {
 366             Ok(Res { val: TAG_IMPLICIT_LEN[tag.val] as uint, next: tag.next })
 367         } else {
 368             vuint_at(data, tag.next)
 369         }
 370     }
 371
 372     pub fn doc_at<'a>(data: &'a [u8], start: uint) -> DecodeResult<TaggedDoc<'a>> {
 373         let elt_tag = try!(tag_at(data, start));
 374         let elt_size = try!(tag_len_at(data, elt_tag));
 375         let end = elt_size.next + elt_size.val;
 376         Ok(TaggedDoc {
 377             tag: elt_tag.val,
 378             doc: Doc { data: data, start: elt_size.next, end: end }
 379         })
 380     }
 381
 382     pub fn maybe_get_doc<'a>(d: Doc<'a>, tg: uint) -> Option<Doc<'a>> {
 383         let mut pos = d.start;
 384         while pos < d.end {
 385             let elt_tag = try_or!(tag_at(d.data, pos), None);
 386             let elt_size = try_or!(tag_len_at(d.data, elt_tag), None);
 387             pos = elt_size.next + elt_size.val;
 388             if elt_tag.val == tg {
 389                 return Some(Doc { data: d.data, start: elt_size.next,
 390                                   end: pos });
 391             }
 392         }
 393         None
 394     }
 395
 396     pub fn get_doc<'a>(d: Doc<'a>, tg: uint) -> Doc<'a> {
 397         match maybe_get_doc(d, tg) {
 398             Some(d) => d,
 399             None => {
 400                 error!("failed to find block with tag {:?}", tg);
 401                 panic!();
 402             }
 403         }
 404     }
 405
 406     pub fn docs<F>(d: Doc, mut it: F) -> bool where
 407         F: FnMut(uint, Doc) -> bool,
 408     {
 409         let mut pos = d.start;
 410         while pos < d.end {
 411             let elt_tag = try_or!(tag_at(d.data, pos), false);
 412             let elt_size = try_or!(tag_len_at(d.data, elt_tag), false);
 413             pos = elt_size.next + elt_size.val;
 414             let doc = Doc { data: d.data, start: elt_size.next, end: pos };
 415             if !it(elt_tag.val, doc) {
 416                 return false;
 417             }
 418         }
 419         return true;
 420     }
 421
 422     pub fn tagged_docs<F>(d: Doc, tg: uint, mut it: F) -> bool where
 423         F: FnMut(Doc) -> bool,
 424     {
 425         let mut pos = d.start;
 426         while pos < d.end {
 427             let elt_tag = try_or!(tag_at(d.data, pos), false);
 428             let elt_size = try_or!(tag_len_at(d.data, elt_tag), false);
 429             pos = elt_size.next + elt_size.val;
 430             if elt_tag.val == tg {
 431                 let doc = Doc { data: d.data, start: elt_size.next,
 432                                 end: pos };
 433                 if !it(doc) {
 434                     return false;
 435                 }
 436             }
 437         }
 438         return true;
 439     }
 440
 441     pub fn with_doc_data<T, F>(d: Doc, f: F) -> T where
 442         F: FnOnce(&[u8]) -> T,
 443     {
 444         f(&d.data[d.start..d.end])
 445     }
 446
 447
 448     pub fn doc_as_u8(d: Doc) -> u8 {
 449         assert_eq!(d.end, d.start + 1);
 450         d.data[d.start]
 451     }
 452
 453     pub fn doc_as_u16(d: Doc) -> u16 {
 454         assert_eq!(d.end, d.start + 2);
 455         let mut b = [0; 2];
 456         bytes::copy_memory(&mut b, &d.data[d.start..d.end]);
 457         unsafe { (*(b.as_ptr() as *const u16)).to_be() }
 458     }
 459
 460     pub fn doc_as_u32(d: Doc) -> u32 {
 461         assert_eq!(d.end, d.start + 4);
 462         let mut b = [0; 4];
 463         bytes::copy_memory(&mut b, &d.data[d.start..d.end]);
 464         unsafe { (*(b.as_ptr() as *const u32)).to_be() }
 465     }
 466
 467     pub fn doc_as_u64(d: Doc) -> u64 {
 468         assert_eq!(d.end, d.start + 8);
 469         let mut b = [0; 8];
 470         bytes::copy_memory(&mut b, &d.data[d.start..d.end]);
 471         unsafe { (*(b.as_ptr() as *const u64)).to_be() }
 472     }
 473
 474     pub fn doc_as_i8(d: Doc) -> i8 { doc_as_u8(d) as i8 }
 475     pub fn doc_as_i16(d: Doc) -> i16 { doc_as_u16(d) as i16 }
 476     pub fn doc_as_i32(d: Doc) -> i32 { doc_as_u32(d) as i32 }
 477     pub fn doc_as_i64(d: Doc) -> i64 { doc_as_u64(d) as i64 }
 478
 479     pub struct Decoder<'a> {
 480         parent: Doc<'a>,
 481         pos: uint,
 482     }
 483
 484     impl<'doc> Decoder<'doc> {
 485         pub fn new(d: Doc<'doc>) -> Decoder<'doc> {
 486             Decoder {
 487                 parent: d,
 488                 pos: d.start
 489             }
 490         }
 491
 492         fn next_doc(&mut self, exp_tag: EbmlEncoderTag) -> DecodeResult<Doc<'doc>> {
 493             debug!(". next_doc(exp_tag={:?})", exp_tag);
 494             if self.pos >= self.parent.end {
 495                 return Err(Expected(format!("no more documents in \
 496                                              current node!")));
 497             }
 498             let TaggedDoc { tag: r_tag, doc: r_doc } =
 499                 try!(doc_at(self.parent.data, self.pos));
 500             debug!("self.parent={:?}-{:?} self.pos={:?} r_tag={:?} r_doc={:?}-{:?}",
 501                    self.parent.start,
 502                    self.parent.end,
 503                    self.pos,
 504                    r_tag,
 505                    r_doc.start,
 506                    r_doc.end);
 507             if r_tag != (exp_tag as uint) {
 508                 return Err(Expected(format!("expected EBML doc with tag {:?} but \
 509                                              found tag {:?}", exp_tag, r_tag)));
 510             }
 511             if r_doc.end > self.parent.end {
 512                 return Err(Expected(format!("invalid EBML, child extends to \
 513                                              {:#x}, parent to {:#x}",
 514                                             r_doc.end, self.parent.end)));
 515             }
 516             self.pos = r_doc.end;
 517             Ok(r_doc)
 518         }
 519
 520         fn push_doc<T, F>(&mut self, exp_tag: EbmlEncoderTag, f: F) -> DecodeResult<T> where
 521             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 522         {
 523             let d = try!(self.next_doc(exp_tag));
 524             let old_parent = self.parent;
 525             let old_pos = self.pos;
 526             self.parent = d;
 527             self.pos = d.start;
 528             let r = try!(f(self));
 529             self.parent = old_parent;
 530             self.pos = old_pos;
 531             Ok(r)
 532         }
 533
 534         fn _next_sub(&mut self) -> DecodeResult<uint> {
 535             // empty vector/map optimization
 536             if self.parent.is_empty() {
 537                 return Ok(0);
 538             }
 539
 540             let TaggedDoc { tag: r_tag, doc: r_doc } =
 541                 try!(doc_at(self.parent.data, self.pos));
 542             let r = if r_tag == (EsSub8 as uint) {
 543                 doc_as_u8(r_doc) as uint
 544             } else if r_tag == (EsSub32 as uint) {
 545                 doc_as_u32(r_doc) as uint
 546             } else {
 547                 return Err(Expected(format!("expected EBML doc with tag {:?} or {:?} but \
 548                                              found tag {:?}", EsSub8, EsSub32, r_tag)));
 549             };
 550             if r_doc.end > self.parent.end {
 551                 return Err(Expected(format!("invalid EBML, child extends to \
 552                                              {:#x}, parent to {:#x}",
 553                                             r_doc.end, self.parent.end)));
 554             }
 555             self.pos = r_doc.end;
 556             debug!("_next_sub result={:?}", r);
 557             Ok(r)
 558         }
 559
 560         // variable-length unsigned integer with different tags.
 561         // `first_tag` should be a tag for u8 or i8.
 562         // `last_tag` should be the largest allowed integer tag with the matching signedness.
 563         // all tags between them should be valid, in the order of u8, u16, u32 and u64.
 564         fn _next_int(&mut self,
 565                      first_tag: EbmlEncoderTag,
 566                      last_tag: EbmlEncoderTag) -> DecodeResult<u64> {
 567             if self.pos >= self.parent.end {
 568                 return Err(Expected(format!("no more documents in \
 569                                              current node!")));
 570             }
 571
 572             let TaggedDoc { tag: r_tag, doc: r_doc } =
 573                 try!(doc_at(self.parent.data, self.pos));
 574             let r = if first_tag as uint <= r_tag && r_tag <= last_tag as uint {
 575                 match r_tag - first_tag as uint {
 576                     0 => doc_as_u8(r_doc) as u64,
 577                     1 => doc_as_u16(r_doc) as u64,
 578                     2 => doc_as_u32(r_doc) as u64,
 579                     3 => doc_as_u64(r_doc) as u64,
 580                     _ => unreachable!(),
 581                 }
 582             } else {
 583                 return Err(Expected(format!("expected EBML doc with tag {:?} through {:?} but \
 584                                              found tag {:?}", first_tag, last_tag, r_tag)));
 585             };
 586             if r_doc.end > self.parent.end {
 587                 return Err(Expected(format!("invalid EBML, child extends to \
 588                                              {:#x}, parent to {:#x}",
 589                                             r_doc.end, self.parent.end)));
 590             }
 591             self.pos = r_doc.end;
 592             debug!("_next_int({:?}, {:?}) result={:?}", first_tag, last_tag, r);
 593             Ok(r)
 594         }
 595
 596         pub fn read_opaque<R, F>(&mut self, op: F) -> DecodeResult<R> where
 597             F: FnOnce(&mut Decoder, Doc) -> DecodeResult<R>,
 598         {
 599             let doc = try!(self.next_doc(EsOpaque));
 600
 601             let (old_parent, old_pos) = (self.parent, self.pos);
 602             self.parent = doc;
 603             self.pos = doc.start;
 604
 605             let result = try!(op(self, doc));
 606
 607             self.parent = old_parent;
 608             self.pos = old_pos;
 609             Ok(result)
 610         }
 611     }
 612
 613     impl<'doc> serialize::Decoder for Decoder<'doc> {
 614         type Error = Error;
 615         fn read_nil(&mut self) -> DecodeResult<()> { Ok(()) }
 616
 617         fn read_u64(&mut self) -> DecodeResult<u64> { self._next_int(EsU8, EsU64) }
 618         fn read_u32(&mut self) -> DecodeResult<u32> { Ok(try!(self._next_int(EsU8, EsU32)) as u32) }
 619         fn read_u16(&mut self) -> DecodeResult<u16> { Ok(try!(self._next_int(EsU8, EsU16)) as u16) }
 620         fn read_u8(&mut self) -> DecodeResult<u8> { Ok(doc_as_u8(try!(self.next_doc(EsU8)))) }
 621         fn read_uint(&mut self) -> DecodeResult<uint> {
 622             let v = try!(self._next_int(EsU8, EsU64));
 623             if v > (::std::usize::MAX as u64) {
 624                 Err(IntTooBig(v as uint))
 625             } else {
 626                 Ok(v as uint)
 627             }
 628         }
 629
 630         fn read_i64(&mut self) -> DecodeResult<i64> { Ok(try!(self._next_int(EsI8, EsI64)) as i64) }
 631         fn read_i32(&mut self) -> DecodeResult<i32> { Ok(try!(self._next_int(EsI8, EsI32)) as i32) }
 632         fn read_i16(&mut self) -> DecodeResult<i16> { Ok(try!(self._next_int(EsI8, EsI16)) as i16) }
 633         fn read_i8(&mut self) -> DecodeResult<i8> { Ok(doc_as_u8(try!(self.next_doc(EsI8))) as i8) }
 634         fn read_int(&mut self) -> DecodeResult<int> {
 635             let v = try!(self._next_int(EsI8, EsI64)) as i64;
 636             if v > (isize::MAX as i64) || v < (isize::MIN as i64) {
 637                 debug!("FIXME \\#6122: Removing this makes this function miscompile");
 638                 Err(IntTooBig(v as uint))
 639             } else {
 640                 Ok(v as int)
 641             }
 642         }
 643
 644         fn read_bool(&mut self) -> DecodeResult<bool> {
 645             Ok(doc_as_u8(try!(self.next_doc(EsBool))) != 0)
 646         }
 647
 648         fn read_f64(&mut self) -> DecodeResult<f64> {
 649             let bits = doc_as_u64(try!(self.next_doc(EsF64)));
 650             Ok(unsafe { transmute(bits) })
 651         }
 652         fn read_f32(&mut self) -> DecodeResult<f32> {
 653             let bits = doc_as_u32(try!(self.next_doc(EsF32)));
 654             Ok(unsafe { transmute(bits) })
 655         }
 656         fn read_char(&mut self) -> DecodeResult<char> {
 657             Ok(char::from_u32(doc_as_u32(try!(self.next_doc(EsChar)))).unwrap())
 658         }
 659         fn read_str(&mut self) -> DecodeResult<String> {
 660             Ok(try!(self.next_doc(EsStr)).as_str())
 661         }
 662
 663         // Compound types:
 664         fn read_enum<T, F>(&mut self, name: &str, f: F) -> DecodeResult<T> where
 665             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 666         {
 667             debug!("read_enum({})", name);
 668
 669             let doc = try!(self.next_doc(EsEnum));
 670
 671             let (old_parent, old_pos) = (self.parent, self.pos);
 672             self.parent = doc;
 673             self.pos = self.parent.start;
 674
 675             let result = try!(f(self));
 676
 677             self.parent = old_parent;
 678             self.pos = old_pos;
 679             Ok(result)
 680         }
 681
 682         fn read_enum_variant<T, F>(&mut self, _: &[&str],
 683                                    mut f: F) -> DecodeResult<T>
 684             where F: FnMut(&mut Decoder<'doc>, uint) -> DecodeResult<T>,
 685         {
 686             debug!("read_enum_variant()");
 687             let idx = try!(self._next_sub());
 688             debug!("  idx={}", idx);
 689
 690             f(self, idx)
 691         }
 692
 693         fn read_enum_variant_arg<T, F>(&mut self, idx: uint, f: F) -> DecodeResult<T> where
 694             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 695         {
 696             debug!("read_enum_variant_arg(idx={})", idx);
 697             f(self)
 698         }
 699
 700         fn read_enum_struct_variant<T, F>(&mut self, _: &[&str],
 701                                           mut f: F) -> DecodeResult<T>
 702             where F: FnMut(&mut Decoder<'doc>, uint) -> DecodeResult<T>,
 703         {
 704             debug!("read_enum_struct_variant()");
 705             let idx = try!(self._next_sub());
 706             debug!("  idx={}", idx);
 707
 708             f(self, idx)
 709         }
 710
 711         fn read_enum_struct_variant_field<T, F>(&mut self,
 712                                                 name: &str,
 713                                                 idx: uint,
 714                                                 f: F)
 715                                                 -> DecodeResult<T> where
 716             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 717         {
 718                 debug!("read_enum_struct_variant_arg(name={}, idx={})", name, idx);
 719             f(self)
 720         }
 721
 722         fn read_struct<T, F>(&mut self, name: &str, _: uint, f: F) -> DecodeResult<T> where
 723             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 724         {
 725             debug!("read_struct(name={})", name);
 726             f(self)
 727         }
 728
 729         fn read_struct_field<T, F>(&mut self, name: &str, idx: uint, f: F) -> DecodeResult<T> where
 730             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 731         {
 732             debug!("read_struct_field(name={}, idx={})", name, idx);
 733             f(self)
 734         }
 735
 736         fn read_tuple<T, F>(&mut self, tuple_len: uint, f: F) -> DecodeResult<T> where
 737             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 738         {
 739             debug!("read_tuple()");
 740             self.read_seq(move |d, len| {
 741                 if len == tuple_len {
 742                     f(d)
 743                 } else {
 744                     Err(Expected(format!("Expected tuple of length `{}`, \
 745                                           found tuple of length `{}`", tuple_len, len)))
 746                 }
 747             })
 748         }
 749
 750         fn read_tuple_arg<T, F>(&mut self, idx: uint, f: F) -> DecodeResult<T> where
 751             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 752         {
 753             debug!("read_tuple_arg(idx={})", idx);
 754             self.read_seq_elt(idx, f)
 755         }
 756
 757         fn read_tuple_struct<T, F>(&mut self, name: &str, len: uint, f: F) -> DecodeResult<T> where
 758             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 759         {
 760             debug!("read_tuple_struct(name={})", name);
 761             self.read_tuple(len, f)
 762         }
 763
 764         fn read_tuple_struct_arg<T, F>(&mut self,
 765                                        idx: uint,
 766                                        f: F)
 767                                        -> DecodeResult<T> where
 768             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 769         {
 770             debug!("read_tuple_struct_arg(idx={})", idx);
 771             self.read_tuple_arg(idx, f)
 772         }
 773
 774         fn read_option<T, F>(&mut self, mut f: F) -> DecodeResult<T> where
 775             F: FnMut(&mut Decoder<'doc>, bool) -> DecodeResult<T>,
 776         {
 777             debug!("read_option()");
 778             self.read_enum("Option", move |this| {
 779                 this.read_enum_variant(&["None", "Some"], move |this, idx| {
 780                     match idx {
 781                         0 => f(this, false),
 782                         1 => f(this, true),
 783                         _ => {
 784                             Err(Expected(format!("Expected None or Some")))
 785                         }
 786                     }
 787                 })
 788             })
 789         }
 790
 791         fn read_seq<T, F>(&mut self, f: F) -> DecodeResult<T> where
 792             F: FnOnce(&mut Decoder<'doc>, uint) -> DecodeResult<T>,
 793         {
 794             debug!("read_seq()");
 795             self.push_doc(EsVec, move |d| {
 796                 let len = try!(d._next_sub());
 797                 debug!("  len={}", len);
 798                 f(d, len)
 799             })
 800         }
 801
 802         fn read_seq_elt<T, F>(&mut self, idx: uint, f: F) -> DecodeResult<T> where
 803             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 804         {
 805             debug!("read_seq_elt(idx={})", idx);
 806             self.push_doc(EsVecElt, f)
 807         }
 808
 809         fn read_map<T, F>(&mut self, f: F) -> DecodeResult<T> where
 810             F: FnOnce(&mut Decoder<'doc>, uint) -> DecodeResult<T>,
 811         {
 812             debug!("read_map()");
 813             self.push_doc(EsMap, move |d| {
 814                 let len = try!(d._next_sub());
 815                 debug!("  len={}", len);
 816                 f(d, len)
 817             })
 818         }
 819
 820         fn read_map_elt_key<T, F>(&mut self, idx: uint, f: F) -> DecodeResult<T> where
 821             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 822         {
 823             debug!("read_map_elt_key(idx={})", idx);
 824             self.push_doc(EsMapKey, f)
 825         }
 826
 827         fn read_map_elt_val<T, F>(&mut self, idx: uint, f: F) -> DecodeResult<T> where
 828             F: FnOnce(&mut Decoder<'doc>) -> DecodeResult<T>,
 829         {
 830             debug!("read_map_elt_val(idx={})", idx);
 831             self.push_doc(EsMapVal, f)
 832         }
 833
 834         fn error(&mut self, err: &str) -> Error {
 835             ApplicationError(err.to_string())
 836         }
 837     }
 838 }
 839
 840 pub mod writer {
 841     use std::mem;
 842     use std::num::Int;
 843     use std::old_io::{Writer, Seek};
 844     use std::old_io;
 845     use std::slice::bytes;
 846     use std::num::ToPrimitive;
 847
 848     use super::{ EsVec, EsMap, EsEnum, EsSub8, EsSub32, EsVecElt, EsMapKey,
 849         EsU64, EsU32, EsU16, EsU8, EsI64, EsI32, EsI16, EsI8,
 850         EsBool, EsF64, EsF32, EsChar, EsStr, EsMapVal,
 851         EsOpaque, NUM_IMPLICIT_TAGS, NUM_TAGS };
 852     use super::io::SeekableMemWriter;
 853
 854     use serialize;
 855
 856
 857     pub type EncodeResult = old_io::IoResult<()>;
 858
 859     // rbml writing
 860     pub struct Encoder<'a> {
 861         pub writer: &'a mut SeekableMemWriter,
 862         size_positions: Vec<uint>,
 863         relax_limit: u64, // do not move encoded bytes before this position
 864     }
 865
 866     fn write_tag<W: Writer>(w: &mut W, n: uint) -> EncodeResult {
 867         if n < 0xf0 {
 868             w.write_all(&[n as u8])
 869         } else if 0x100 <= n && n < NUM_TAGS {
 870             w.write_all(&[0xf0 | (n >> 8) as u8, n as u8])
 871         } else {
 872             Err(old_io::IoError {
 873                 kind: old_io::OtherIoError,
 874                 desc: "invalid tag",
 875                 detail: Some(format!("{}", n))
 876             })
 877         }
 878     }
 879
 880     fn write_sized_vuint<W: Writer>(w: &mut W, n: uint, size: uint) -> EncodeResult {
 881         match size {
 882             1 => w.write_all(&[0x80 | (n as u8)]),
 883             2 => w.write_all(&[0x40 | ((n >> 8) as u8), n as u8]),
 884             3 => w.write_all(&[0x20 | ((n >> 16) as u8), (n >> 8) as u8,
 885                             n as u8]),
 886             4 => w.write_all(&[0x10 | ((n >> 24) as u8), (n >> 16) as u8,
 887                             (n >> 8) as u8, n as u8]),
 888             _ => Err(old_io::IoError {
 889                 kind: old_io::OtherIoError,
 890                 desc: "int too big",
 891                 detail: Some(format!("{}", n))
 892             })
 893         }
 894     }
 895
 896     fn write_vuint<W: Writer>(w: &mut W, n: uint) -> EncodeResult {
 897         if n < 0x7f { return write_sized_vuint(w, n, 1); }
 898         if n < 0x4000 { return write_sized_vuint(w, n, 2); }
 899         if n < 0x200000 { return write_sized_vuint(w, n, 3); }
 900         if n < 0x10000000 { return write_sized_vuint(w, n, 4); }
 901         Err(old_io::IoError {
 902             kind: old_io::OtherIoError,
 903             desc: "int too big",
 904             detail: Some(format!("{}", n))
 905         })
 906     }
 907
 908     impl<'a> Encoder<'a> {
 909         pub fn new(w: &'a mut SeekableMemWriter) -> Encoder<'a> {
 910             Encoder {
 911                 writer: w,
 912                 size_positions: vec!(),
 913                 relax_limit: 0,
 914             }
 915         }
 916
 917         /// FIXME(pcwalton): Workaround for badness in trans. DO NOT USE ME.
 918         pub unsafe fn unsafe_clone(&self) -> Encoder<'a> {
 919             Encoder {
 920                 writer: mem::transmute_copy(&self.writer),
 921                 size_positions: self.size_positions.clone(),
 922                 relax_limit: self.relax_limit,
 923             }
 924         }
 925
 926         pub fn start_tag(&mut self, tag_id: uint) -> EncodeResult {
 927             debug!("Start tag {:?}", tag_id);
 928             assert!(tag_id >= NUM_IMPLICIT_TAGS);
 929
 930             // Write the enum ID:
 931             try!(write_tag(self.writer, tag_id));
 932
 933             // Write a placeholder four-byte size.
 934             self.size_positions.push(try!(self.writer.tell()) as uint);
 935             let zeroes: &[u8] = &[0, 0, 0, 0];
 936             self.writer.write_all(zeroes)
 937         }
 938
 939         pub fn end_tag(&mut self) -> EncodeResult {
 940             let last_size_pos = self.size_positions.pop().unwrap();
 941             let cur_pos = try!(self.writer.tell());
 942             try!(self.writer.seek(last_size_pos as i64, old_io::SeekSet));
 943             let size = cur_pos as uint - last_size_pos - 4;
 944
 945             // relax the size encoding for small tags (bigger tags are costly to move).
 946             // we should never try to move the stable positions, however.
 947             const RELAX_MAX_SIZE: uint = 0x100;
 948             if size <= RELAX_MAX_SIZE && last_size_pos >= self.relax_limit as uint {
 949                 // we can't alter the buffer in place, so have a temporary buffer
 950                 let mut buf = [0u8; RELAX_MAX_SIZE];
 951                 {
 952                     let data = &self.writer.get_ref()[last_size_pos+4..cur_pos as uint];
 953                     bytes::copy_memory(&mut buf, data);
 954                 }
 955
 956                 // overwrite the size and data and continue
 957                 try!(write_vuint(self.writer, size));
 958                 try!(self.writer.write_all(&buf[..size]));
 959             } else {
 960                 // overwrite the size with an overlong encoding and skip past the data
 961                 try!(write_sized_vuint(self.writer, size, 4));
 962                 try!(self.writer.seek(cur_pos as i64, old_io::SeekSet));
 963             }
 964
 965             debug!("End tag (size = {:?})", size);
 966             Ok(())
 967         }
 968
 969         pub fn wr_tag<F>(&mut self, tag_id: uint, blk: F) -> EncodeResult where
 970             F: FnOnce() -> EncodeResult,
 971         {
 972             try!(self.start_tag(tag_id));
 973             try!(blk());
 974             self.end_tag()
 975         }
 976
 977         pub fn wr_tagged_bytes(&mut self, tag_id: uint, b: &[u8]) -> EncodeResult {
 978             assert!(tag_id >= NUM_IMPLICIT_TAGS);
 979             try!(write_tag(self.writer, tag_id));
 980             try!(write_vuint(self.writer, b.len()));
 981             self.writer.write_all(b)
 982         }
 983
 984         pub fn wr_tagged_u64(&mut self, tag_id: uint, v: u64) -> EncodeResult {
 985             let bytes: [u8; 8] = unsafe { mem::transmute(v.to_be()) };
 986             self.wr_tagged_bytes(tag_id, &bytes)
 987         }
 988
 989         pub fn wr_tagged_u32(&mut self, tag_id: uint, v: u32)  -> EncodeResult{
 990             let bytes: [u8; 4] = unsafe { mem::transmute(v.to_be()) };
 991             self.wr_tagged_bytes(tag_id, &bytes)
 992         }
 993
 994         pub fn wr_tagged_u16(&mut self, tag_id: uint, v: u16) -> EncodeResult {
 995             let bytes: [u8; 2] = unsafe { mem::transmute(v.to_be()) };
 996             self.wr_tagged_bytes(tag_id, &bytes)
 997         }
 998
 999         pub fn wr_tagged_u8(&mut self, tag_id: uint, v: u8) -> EncodeResult {
1000             self.wr_tagged_bytes(tag_id, &[v])
1001         }
1002
1003         pub fn wr_tagged_i64(&mut self, tag_id: uint, v: i64) -> EncodeResult {
1004             self.wr_tagged_u64(tag_id, v as u64)
1005         }
1006
1007         pub fn wr_tagged_i32(&mut self, tag_id: uint, v: i32) -> EncodeResult {
1008             self.wr_tagged_u32(tag_id, v as u32)
1009         }
1010
1011         pub fn wr_tagged_i16(&mut self, tag_id: uint, v: i16) -> EncodeResult {
1012             self.wr_tagged_u16(tag_id, v as u16)
1013         }
1014
1015         pub fn wr_tagged_i8(&mut self, tag_id: uint, v: i8) -> EncodeResult {
1016             self.wr_tagged_bytes(tag_id, &[v as u8])
1017         }
1018
1019         pub fn wr_tagged_str(&mut self, tag_id: uint, v: &str) -> EncodeResult {
1020             self.wr_tagged_bytes(tag_id, v.as_bytes())
1021         }
1022
1023         // for auto-serialization
1024         fn wr_tagged_raw_bytes(&mut self, tag_id: uint, b: &[u8]) -> EncodeResult {
1025             try!(write_tag(self.writer, tag_id));
1026             self.writer.write_all(b)
1027         }
1028
1029         fn wr_tagged_raw_u64(&mut self, tag_id: uint, v: u64) -> EncodeResult {
1030             let bytes: [u8; 8] = unsafe { mem::transmute(v.to_be()) };
1031             self.wr_tagged_raw_bytes(tag_id, &bytes)
1032         }
1033
1034         fn wr_tagged_raw_u32(&mut self, tag_id: uint, v: u32)  -> EncodeResult{
1035             let bytes: [u8; 4] = unsafe { mem::transmute(v.to_be()) };
1036             self.wr_tagged_raw_bytes(tag_id, &bytes)
1037         }
1038
1039         fn wr_tagged_raw_u16(&mut self, tag_id: uint, v: u16) -> EncodeResult {
1040             let bytes: [u8; 2] = unsafe { mem::transmute(v.to_be()) };
1041             self.wr_tagged_raw_bytes(tag_id, &bytes)
1042         }
1043
1044         fn wr_tagged_raw_u8(&mut self, tag_id: uint, v: u8) -> EncodeResult {
1045             self.wr_tagged_raw_bytes(tag_id, &[v])
1046         }
1047
1048         fn wr_tagged_raw_i64(&mut self, tag_id: uint, v: i64) -> EncodeResult {
1049             self.wr_tagged_raw_u64(tag_id, v as u64)
1050         }
1051
1052         fn wr_tagged_raw_i32(&mut self, tag_id: uint, v: i32) -> EncodeResult {
1053             self.wr_tagged_raw_u32(tag_id, v as u32)
1054         }
1055
1056         fn wr_tagged_raw_i16(&mut self, tag_id: uint, v: i16) -> EncodeResult {
1057             self.wr_tagged_raw_u16(tag_id, v as u16)
1058         }
1059
1060         fn wr_tagged_raw_i8(&mut self, tag_id: uint, v: i8) -> EncodeResult {
1061             self.wr_tagged_raw_bytes(tag_id, &[v as u8])
1062         }
1063
1064         pub fn wr_bytes(&mut self, b: &[u8]) -> EncodeResult {
1065             debug!("Write {:?} bytes", b.len());
1066             self.writer.write_all(b)
1067         }
1068
1069         pub fn wr_str(&mut self, s: &str) -> EncodeResult {
1070             debug!("Write str: {:?}", s);
1071             self.writer.write_all(s.as_bytes())
1072         }
1073
1074         /// Returns the current position while marking it stable, i.e.
1075         /// generated bytes so far woundn't be affected by relaxation.
1076         pub fn mark_stable_position(&mut self) -> u64 {
1077             let pos = self.writer.tell().unwrap();
1078             if self.relax_limit < pos {
1079                 self.relax_limit = pos;
1080             }
1081             pos
1082         }
1083     }
1084
1085     impl<'a> Encoder<'a> {
1086         // used internally to emit things like the vector length and so on
1087         fn _emit_tagged_sub(&mut self, v: uint) -> EncodeResult {
1088             if let Some(v) = v.to_u8() {
1089                 self.wr_tagged_raw_u8(EsSub8 as uint, v)
1090             } else if let Some(v) = v.to_u32() {
1091                 self.wr_tagged_raw_u32(EsSub32 as uint, v)
1092             } else {
1093                 Err(old_io::IoError {
1094                     kind: old_io::OtherIoError,
1095                     desc: "length or variant id too big",
1096                     detail: Some(format!("{}", v))
1097                 })
1098             }
1099         }
1100
1101         pub fn emit_opaque<F>(&mut self, f: F) -> EncodeResult where
1102             F: FnOnce(&mut Encoder) -> EncodeResult,
1103         {
1104             try!(self.start_tag(EsOpaque as uint));
1105             try!(f(self));
1106             self.end_tag()
1107         }
1108     }
1109
1110     impl<'a> serialize::Encoder for Encoder<'a> {
1111         type Error = old_io::IoError;
1112
1113         fn emit_nil(&mut self) -> EncodeResult {
1114             Ok(())
1115         }
1116
1117         fn emit_uint(&mut self, v: uint) -> EncodeResult {
1118             self.emit_u64(v as u64)
1119         }
1120         fn emit_u64(&mut self, v: u64) -> EncodeResult {
1121             match v.to_u32() {
1122                 Some(v) => self.emit_u32(v),
1123                 None => self.wr_tagged_raw_u64(EsU64 as uint, v)
1124             }
1125         }
1126         fn emit_u32(&mut self, v: u32) -> EncodeResult {
1127             match v.to_u16() {
1128                 Some(v) => self.emit_u16(v),
1129                 None => self.wr_tagged_raw_u32(EsU32 as uint, v)
1130             }
1131         }
1132         fn emit_u16(&mut self, v: u16) -> EncodeResult {
1133             match v.to_u8() {
1134                 Some(v) => self.emit_u8(v),
1135                 None => self.wr_tagged_raw_u16(EsU16 as uint, v)
1136             }
1137         }
1138         fn emit_u8(&mut self, v: u8) -> EncodeResult {
1139             self.wr_tagged_raw_u8(EsU8 as uint, v)
1140         }
1141
1142         fn emit_int(&mut self, v: int) -> EncodeResult {
1143             self.emit_i64(v as i64)
1144         }
1145         fn emit_i64(&mut self, v: i64) -> EncodeResult {
1146             match v.to_i32() {
1147                 Some(v) => self.emit_i32(v),
1148                 None => self.wr_tagged_raw_i64(EsI64 as uint, v)
1149             }
1150         }
1151         fn emit_i32(&mut self, v: i32) -> EncodeResult {
1152             match v.to_i16() {
1153                 Some(v) => self.emit_i16(v),
1154                 None => self.wr_tagged_raw_i32(EsI32 as uint, v)
1155             }
1156         }
1157         fn emit_i16(&mut self, v: i16) -> EncodeResult {
1158             match v.to_i8() {
1159                 Some(v) => self.emit_i8(v),
1160                 None => self.wr_tagged_raw_i16(EsI16 as uint, v)
1161             }
1162         }
1163         fn emit_i8(&mut self, v: i8) -> EncodeResult {
1164             self.wr_tagged_raw_i8(EsI8 as uint, v)
1165         }
1166
1167         fn emit_bool(&mut self, v: bool) -> EncodeResult {
1168             self.wr_tagged_raw_u8(EsBool as uint, v as u8)
1169         }
1170
1171         fn emit_f64(&mut self, v: f64) -> EncodeResult {
1172             let bits = unsafe { mem::transmute(v) };
1173             self.wr_tagged_raw_u64(EsF64 as uint, bits)
1174         }
1175         fn emit_f32(&mut self, v: f32) -> EncodeResult {
1176             let bits = unsafe { mem::transmute(v) };
1177             self.wr_tagged_raw_u32(EsF32 as uint, bits)
1178         }
1179         fn emit_char(&mut self, v: char) -> EncodeResult {
1180             self.wr_tagged_raw_u32(EsChar as uint, v as u32)
1181         }
1182
1183         fn emit_str(&mut self, v: &str) -> EncodeResult {
1184             self.wr_tagged_str(EsStr as uint, v)
1185         }
1186
1187         fn emit_enum<F>(&mut self, _name: &str, f: F) -> EncodeResult where
1188             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1189         {
1190             try!(self.start_tag(EsEnum as uint));
1191             try!(f(self));
1192             self.end_tag()
1193         }
1194
1195         fn emit_enum_variant<F>(&mut self,
1196                                 _: &str,
1197                                 v_id: uint,
1198                                 _: uint,
1199                                 f: F) -> EncodeResult where
1200             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1201         {
1202             try!(self._emit_tagged_sub(v_id));
1203             f(self)
1204         }
1205
1206         fn emit_enum_variant_arg<F>(&mut self, _: uint, f: F) -> EncodeResult where
1207             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1208         {
1209             f(self)
1210         }
1211
1212         fn emit_enum_struct_variant<F>(&mut self,
1213                                        v_name: &str,
1214                                        v_id: uint,
1215                                        cnt: uint,
1216                                        f: F) -> EncodeResult where
1217             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1218         {
1219             self.emit_enum_variant(v_name, v_id, cnt, f)
1220         }
1221
1222         fn emit_enum_struct_variant_field<F>(&mut self,
1223                                              _: &str,
1224                                              idx: uint,
1225                                              f: F) -> EncodeResult where
1226             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1227         {
1228             self.emit_enum_variant_arg(idx, f)
1229         }
1230
1231         fn emit_struct<F>(&mut self, _: &str, _len: uint, f: F) -> EncodeResult where
1232             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1233         {
1234             f(self)
1235         }
1236
1237         fn emit_struct_field<F>(&mut self, _name: &str, _: uint, f: F) -> EncodeResult where
1238             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1239         {
1240             f(self)
1241         }
1242
1243         fn emit_tuple<F>(&mut self, len: uint, f: F) -> EncodeResult where
1244             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1245         {
1246             self.emit_seq(len, f)
1247         }
1248         fn emit_tuple_arg<F>(&mut self, idx: uint, f: F) -> EncodeResult where
1249             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1250         {
1251             self.emit_seq_elt(idx, f)
1252         }
1253
1254         fn emit_tuple_struct<F>(&mut self, _: &str, len: uint, f: F) -> EncodeResult where
1255             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1256         {
1257             self.emit_seq(len, f)
1258         }
1259         fn emit_tuple_struct_arg<F>(&mut self, idx: uint, f: F) -> EncodeResult where
1260             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1261         {
1262             self.emit_seq_elt(idx, f)
1263         }
1264
1265         fn emit_option<F>(&mut self, f: F) -> EncodeResult where
1266             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1267         {
1268             self.emit_enum("Option", f)
1269         }
1270         fn emit_option_none(&mut self) -> EncodeResult {
1271             self.emit_enum_variant("None", 0, 0, |_| Ok(()))
1272         }
1273         fn emit_option_some<F>(&mut self, f: F) -> EncodeResult where
1274             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1275         {
1276
1277             self.emit_enum_variant("Some", 1, 1, f)
1278         }
1279
1280         fn emit_seq<F>(&mut self, len: uint, f: F) -> EncodeResult where
1281             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1282         {
1283             if len == 0 {
1284                 // empty vector optimization
1285                 return self.wr_tagged_bytes(EsVec as uint, &[]);
1286             }
1287
1288             try!(self.start_tag(EsVec as uint));
1289             try!(self._emit_tagged_sub(len));
1290             try!(f(self));
1291             self.end_tag()
1292         }
1293
1294         fn emit_seq_elt<F>(&mut self, _idx: uint, f: F) -> EncodeResult where
1295             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1296         {
1297
1298             try!(self.start_tag(EsVecElt as uint));
1299             try!(f(self));
1300             self.end_tag()
1301         }
1302
1303         fn emit_map<F>(&mut self, len: uint, f: F) -> EncodeResult where
1304             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1305         {
1306             if len == 0 {
1307                 // empty map optimization
1308                 return self.wr_tagged_bytes(EsMap as uint, &[]);
1309             }
1310
1311             try!(self.start_tag(EsMap as uint));
1312             try!(self._emit_tagged_sub(len));
1313             try!(f(self));
1314             self.end_tag()
1315         }
1316
1317         fn emit_map_elt_key<F>(&mut self, _idx: uint, f: F) -> EncodeResult where
1318             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1319         {
1320
1321             try!(self.start_tag(EsMapKey as uint));
1322             try!(f(self));
1323             self.end_tag()
1324         }
1325
1326         fn emit_map_elt_val<F>(&mut self, _idx: uint, f: F) -> EncodeResult where
1327             F: FnOnce(&mut Encoder<'a>) -> EncodeResult,
1328         {
1329             try!(self.start_tag(EsMapVal as uint));
1330             try!(f(self));
1331             self.end_tag()
1332         }
1333     }
1334 }
1335
1336 // ___________________________________________________________________________
1337 // Testing
1338
1339 #[cfg(test)]
1340 mod tests {
1341     use super::{Doc, reader, writer};
1342     use super::io::SeekableMemWriter;
1343
1344     use serialize::{Encodable, Decodable};
1345
1346     use std::option::Option;
1347     use std::option::Option::{None, Some};
1348
1349     #[test]
1350     fn test_vuint_at() {
1351         let data = &[
1352             0x80,
1353             0xff,
1354             0x40, 0x00,
1355             0x7f, 0xff,
1356             0x20, 0x00, 0x00,
1357             0x3f, 0xff, 0xff,
1358             0x10, 0x00, 0x00, 0x00,
1359             0x1f, 0xff, 0xff, 0xff
1360         ];
1361
1362         let mut res: reader::Res;
1363
1364         // Class A
1365         res = reader::vuint_at(data, 0).unwrap();
1366         assert_eq!(res.val, 0);
1367         assert_eq!(res.next, 1);
1368         res = reader::vuint_at(data, res.next).unwrap();
1369         assert_eq!(res.val, (1 << 7) - 1);
1370         assert_eq!(res.next, 2);
1371
1372         // Class B
1373         res = reader::vuint_at(data, res.next).unwrap();
1374         assert_eq!(res.val, 0);
1375         assert_eq!(res.next, 4);
1376         res = reader::vuint_at(data, res.next).unwrap();
1377         assert_eq!(res.val, (1 << 14) - 1);
1378         assert_eq!(res.next, 6);
1379
1380         // Class C
1381         res = reader::vuint_at(data, res.next).unwrap();
1382         assert_eq!(res.val, 0);
1383         assert_eq!(res.next, 9);
1384         res = reader::vuint_at(data, res.next).unwrap();
1385         assert_eq!(res.val, (1 << 21) - 1);
1386         assert_eq!(res.next, 12);
1387
1388         // Class D
1389         res = reader::vuint_at(data, res.next).unwrap();
1390         assert_eq!(res.val, 0);
1391         assert_eq!(res.next, 16);
1392         res = reader::vuint_at(data, res.next).unwrap();
1393         assert_eq!(res.val, (1 << 28) - 1);
1394         assert_eq!(res.next, 20);
1395     }
1396
1397     #[test]
1398     fn test_option_int() {
1399         fn test_v(v: Option<int>) {
1400             debug!("v == {:?}", v);
1401             let mut wr = SeekableMemWriter::new();
1402             {
1403                 let mut rbml_w = writer::Encoder::new(&mut wr);
1404                 let _ = v.encode(&mut rbml_w);
1405             }
1406             let rbml_doc = Doc::new(wr.get_ref());
1407             let mut deser = reader::Decoder::new(rbml_doc);
1408             let v1 = Decodable::decode(&mut deser).unwrap();
1409             debug!("v1 == {:?}", v1);
1410             assert_eq!(v, v1);
1411         }
1412
1413         test_v(Some(22));
1414         test_v(None);
1415         test_v(Some(3));
1416     }
1417 }
1418
1419 #[cfg(test)]
1420 mod bench {
1421     #![allow(non_snake_case)]
1422     use test::Bencher;
1423     use super::reader;
1424
1425     #[bench]
1426     pub fn vuint_at_A_aligned(b: &mut Bencher) {
1427         let data = (0..4*100).map(|i| {
1428             match i % 2 {
1429               0 => 0x80,
1430               _ => i as u8,
1431             }
1432         }).collect::<Vec<_>>();
1433         let mut sum = 0;
1434         b.iter(|| {
1435             let mut i = 0;
1436             while i < data.len() {
1437                 sum += reader::vuint_at(&data, i).unwrap().val;
1438                 i += 4;
1439             }
1440         });
1441     }
1442
1443     #[bench]
1444     pub fn vuint_at_A_unaligned(b: &mut Bencher) {
1445         let data = (0..4*100+1).map(|i| {
1446             match i % 2 {
1447               1 => 0x80,
1448               _ => i as u8
1449             }
1450         }).collect::<Vec<_>>();
1451         let mut sum = 0;
1452         b.iter(|| {
1453             let mut i = 1;
1454             while i < data.len() {
1455                 sum += reader::vuint_at(&data, i).unwrap().val;
1456                 i += 4;
1457             }
1458         });
1459     }
1460
1461     #[bench]
1462     pub fn vuint_at_D_aligned(b: &mut Bencher) {
1463         let data = (0..4*100).map(|i| {
1464             match i % 4 {
1465               0 => 0x10,
1466               3 => i as u8,
1467               _ => 0
1468             }
1469         }).collect::<Vec<_>>();
1470         let mut sum = 0;
1471         b.iter(|| {
1472             let mut i = 0;
1473             while i < data.len() {
1474                 sum += reader::vuint_at(&data, i).unwrap().val;
1475                 i += 4;
1476             }
1477         });
1478     }
1479
1480     #[bench]
1481     pub fn vuint_at_D_unaligned(b: &mut Bencher) {
1482         let data = (0..4*100+1).map(|i| {
1483             match i % 4 {
1484               1 => 0x10,
1485               0 => i as u8,
1486               _ => 0
1487             }
1488         }).collect::<Vec<_>>();
1489         let mut sum = 0;
1490         b.iter(|| {
1491             let mut i = 1;
1492             while i < data.len() {
1493                 sum += reader::vuint_at(&data, i).unwrap().val;
1494                 i += 4;
1495             }
1496         });
1497     }
1498 }