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