src/librbml/lib.rs

   1 // Copyright 2012-2014 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 a temporary measure until we migrate
  12 //! the rust object metadata to a better serialization format. It is not
  13 //! intended to be used by users.
  14 //!
  15 //! It is loosely based on the Extensible Binary Markup Language (ebml):
  16 //!     http://www.matroska.org/technical/specs/rfc/index.html
  17
  18 #![crate_name = "rbml"]
  19 #![experimental]
  20 #![crate_type = "rlib"]
  21 #![crate_type = "dylib"]
  22 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  23        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  24        html_root_url = "http://doc.rust-lang.org/nightly/",
  25        html_playground_url = "http://play.rust-lang.org/")]
  26 #![allow(unknown_features)]
  27 #![feature(macro_rules, phase, slicing_syntax, globs)]
  28 #![allow(missing_docs)]
  29
  30 extern crate serialize;
  31
  32 #[phase(plugin, link)] extern crate log;
  33 #[cfg(test)] extern crate test;
  34
  35 pub use self::EbmlEncoderTag::*;
  36 pub use self::Error::*;
  37
  38 use std::str;
  39
  40 pub mod io;
  41
  42 /// Common data structures
  43 #[deriving(Clone)]
  44 pub struct Doc<'a> {
  45     pub data: &'a [u8],
  46     pub start: uint,
  47     pub end: uint,
  48 }
  49
  50 impl<'doc> Doc<'doc> {
  51     pub fn new(data: &'doc [u8]) -> Doc<'doc> {
  52         Doc { data: data, start: 0u, end: data.len() }
  53     }
  54
  55     pub fn get<'a>(&'a self, tag: uint) -> Doc<'a> {
  56         reader::get_doc(*self, tag)
  57     }
  58
  59     pub fn as_str_slice<'a>(&'a self) -> &'a str {
  60         str::from_utf8(self.data[self.start..self.end]).unwrap()
  61     }
  62
  63     pub fn as_str(&self) -> String {
  64         self.as_str_slice().to_string()
  65     }
  66 }
  67
  68 pub struct TaggedDoc<'a> {
  69     tag: uint,
  70     pub doc: Doc<'a>,
  71 }
  72
  73 #[deriving(Show)]
  74 pub enum EbmlEncoderTag {
  75     EsUint,     // 0
  76     EsU64,      // 1
  77     EsU32,      // 2
  78     EsU16,      // 3
  79     EsU8,       // 4
  80     EsInt,      // 5
  81     EsI64,      // 6
  82     EsI32,      // 7
  83     EsI16,      // 8
  84     EsI8,       // 9
  85     EsBool,     // 10
  86     EsChar,     // 11
  87     EsStr,      // 12
  88     EsF64,      // 13
  89     EsF32,      // 14
  90     EsFloat,    // 15
  91     EsEnum,     // 16
  92     EsEnumVid,  // 17
  93     EsEnumBody, // 18
  94     EsVec,      // 19
  95     EsVecLen,   // 20
  96     EsVecElt,   // 21
  97     EsMap,      // 22
  98     EsMapLen,   // 23
  99     EsMapKey,   // 24
 100     EsMapVal,   // 25
 101
 102     EsOpaque,
 103
 104     EsLabel, // Used only when debugging
 105 }
 106
 107 #[deriving(Show)]
 108 pub enum Error {
 109     IntTooBig(uint),
 110     Expected(String),
 111     IoError(std::io::IoError),
 112     ApplicationError(String)
 113 }
 114 // --------------------------------------
 115
 116 pub mod reader {
 117     use std::char;
 118
 119     use std::int;
 120     use std::io::extensions::u64_from_be_bytes;
 121     use std::mem::transmute;
 122     use std::num::Int;
 123     use std::option::Option;
 124     use std::option::Option::{None, Some};
 125
 126     use serialize;
 127
 128     use super::{ ApplicationError, EsVec, EsMap, EsEnum, EsVecLen, EsVecElt,
 129         EsMapLen, EsMapKey, EsEnumVid, EsU64, EsU32, EsU16, EsU8, EsInt, EsI64,
 130         EsI32, EsI16, EsI8, EsBool, EsF64, EsF32, EsChar, EsStr, EsMapVal,
 131         EsEnumBody, EsUint, EsOpaque, EsLabel, EbmlEncoderTag, Doc, TaggedDoc,
 132         Error, IntTooBig, Expected };
 133
 134     pub type DecodeResult<T> = Result<T, Error>;
 135     // rbml reading
 136
 137     macro_rules! try_or(
 138         ($e:expr, $r:expr) => (
 139             match $e {
 140                 Ok(e) => e,
 141                 Err(e) => {
 142                     debug!("ignored error: {}", e);
 143                     return $r
 144                 }
 145             }
 146         )
 147     )
 148
 149     pub struct Res {
 150         pub val: uint,
 151         pub next: uint
 152     }
 153
 154     #[inline(never)]
 155     fn vuint_at_slow(data: &[u8], start: uint) -> DecodeResult<Res> {
 156         let a = data[start];
 157         if a & 0x80u8 != 0u8 {
 158             return Ok(Res {val: (a & 0x7fu8) as uint, next: start + 1u});
 159         }
 160         if a & 0x40u8 != 0u8 {
 161             return Ok(Res {val: ((a & 0x3fu8) as uint) << 8u |
 162                         (data[start + 1u] as uint),
 163                     next: start + 2u});
 164         }
 165         if a & 0x20u8 != 0u8 {
 166             return Ok(Res {val: ((a & 0x1fu8) as uint) << 16u |
 167                         (data[start + 1u] as uint) << 8u |
 168                         (data[start + 2u] as uint),
 169                     next: start + 3u});
 170         }
 171         if a & 0x10u8 != 0u8 {
 172             return Ok(Res {val: ((a & 0x0fu8) as uint) << 24u |
 173                         (data[start + 1u] as uint) << 16u |
 174                         (data[start + 2u] as uint) << 8u |
 175                         (data[start + 3u] as uint),
 176                     next: start + 4u});
 177         }
 178         Err(IntTooBig(a as uint))
 179     }
 180
 181     pub fn vuint_at(data: &[u8], start: uint) -> DecodeResult<Res> {
 182         if data.len() - start < 4 {
 183             return vuint_at_slow(data, start);
 184         }
 185
 186         // Lookup table for parsing EBML Element IDs as per http://ebml.sourceforge.net/specs/
 187         // The Element IDs are parsed by reading a big endian u32 positioned at data[start].
 188         // Using the four most significant bits of the u32 we lookup in the table below how the
 189         // element ID should be derived from it.
 190         //
 191         // The table stores tuples (shift, mask) where shift is the number the u32 should be right
 192         // shifted with and mask is the value the right shifted value should be masked with.
 193         // If for example the most significant bit is set this means it's a class A ID and the u32
 194         // should be right shifted with 24 and masked with 0x7f. Therefore we store (24, 0x7f) at
 195         // index 0x8 - 0xF (four bit numbers where the most significant bit is set).
 196         //
 197         // By storing the number of shifts and masks in a table instead of checking in order if
 198         // the most significant bit is set, the second most significant bit is set etc. we can
 199         // replace up to three "and+branch" with a single table lookup which gives us a measured
 200         // speedup of around 2x on x86_64.
 201         static SHIFT_MASK_TABLE: [(uint, u32), ..16] = [
 202             (0, 0x0), (0, 0x0fffffff),
 203             (8, 0x1fffff), (8, 0x1fffff),
 204             (16, 0x3fff), (16, 0x3fff), (16, 0x3fff), (16, 0x3fff),
 205             (24, 0x7f), (24, 0x7f), (24, 0x7f), (24, 0x7f),
 206             (24, 0x7f), (24, 0x7f), (24, 0x7f), (24, 0x7f)
 207         ];
 208
 209         unsafe {
 210             let ptr = data.as_ptr().offset(start as int) as *const u32;
 211             let val = Int::from_be(*ptr);
 212
 213             let i = (val >> 28u) as uint;
 214             let (shift, mask) = SHIFT_MASK_TABLE[i];
 215             Ok(Res {
 216                 val: ((val >> shift) & mask) as uint,
 217                 next: start + (((32 - shift) >> 3) as uint)
 218             })
 219         }
 220     }
 221
 222     pub fn doc_at<'a>(data: &'a [u8], start: uint) -> DecodeResult<TaggedDoc<'a>> {
 223         let elt_tag = try!(vuint_at(data, start));
 224         let elt_size = try!(vuint_at(data, elt_tag.next));
 225         let end = elt_size.next + elt_size.val;
 226         Ok(TaggedDoc {
 227             tag: elt_tag.val,
 228             doc: Doc { data: data, start: elt_size.next, end: end }
 229         })
 230     }
 231
 232     pub fn maybe_get_doc<'a>(d: Doc<'a>, tg: uint) -> Option<Doc<'a>> {
 233         let mut pos = d.start;
 234         while pos < d.end {
 235             let elt_tag = try_or!(vuint_at(d.data, pos), None);
 236             let elt_size = try_or!(vuint_at(d.data, elt_tag.next), None);
 237             pos = elt_size.next + elt_size.val;
 238             if elt_tag.val == tg {
 239                 return Some(Doc { data: d.data, start: elt_size.next,
 240                                   end: pos });
 241             }
 242         }
 243         None
 244     }
 245
 246     pub fn get_doc<'a>(d: Doc<'a>, tg: uint) -> Doc<'a> {
 247         match maybe_get_doc(d, tg) {
 248             Some(d) => d,
 249             None => {
 250                 error!("failed to find block with tag {}", tg);
 251                 panic!();
 252             }
 253         }
 254     }
 255
 256     pub fn docs<'a>(d: Doc<'a>, it: |uint, Doc<'a>| -> bool) -> bool {
 257         let mut pos = d.start;
 258         while pos < d.end {
 259             let elt_tag = try_or!(vuint_at(d.data, pos), false);
 260             let elt_size = try_or!(vuint_at(d.data, elt_tag.next), false);
 261             pos = elt_size.next + elt_size.val;
 262             let doc = Doc { data: d.data, start: elt_size.next, end: pos };
 263             if !it(elt_tag.val, doc) {
 264                 return false;
 265             }
 266         }
 267         return true;
 268     }
 269
 270     pub fn tagged_docs<'a>(d: Doc<'a>, tg: uint, it: |Doc<'a>| -> bool) -> bool {
 271         let mut pos = d.start;
 272         while pos < d.end {
 273             let elt_tag = try_or!(vuint_at(d.data, pos), false);
 274             let elt_size = try_or!(vuint_at(d.data, elt_tag.next), false);
 275             pos = elt_size.next + elt_size.val;
 276             if elt_tag.val == tg {
 277                 let doc = Doc { data: d.data, start: elt_size.next,
 278                                 end: pos };
 279                 if !it(doc) {
 280                     return false;
 281                 }
 282             }
 283         }
 284         return true;
 285     }
 286
 287     pub fn with_doc_data<'a, T>(d: Doc<'a>, f: |x: &'a [u8]| -> T) -> T {
 288         f(d.data[d.start..d.end])
 289     }
 290
 291
 292     pub fn doc_as_u8(d: Doc) -> u8 {
 293         assert_eq!(d.end, d.start + 1u);
 294         d.data[d.start]
 295     }
 296
 297     pub fn doc_as_u16(d: Doc) -> u16 {
 298         assert_eq!(d.end, d.start + 2u);
 299         u64_from_be_bytes(d.data, d.start, 2u) as u16
 300     }
 301
 302     pub fn doc_as_u32(d: Doc) -> u32 {
 303         assert_eq!(d.end, d.start + 4u);
 304         u64_from_be_bytes(d.data, d.start, 4u) as u32
 305     }
 306
 307     pub fn doc_as_u64(d: Doc) -> u64 {
 308         assert_eq!(d.end, d.start + 8u);
 309         u64_from_be_bytes(d.data, d.start, 8u)
 310     }
 311
 312     pub fn doc_as_i8(d: Doc) -> i8 { doc_as_u8(d) as i8 }
 313     pub fn doc_as_i16(d: Doc) -> i16 { doc_as_u16(d) as i16 }
 314     pub fn doc_as_i32(d: Doc) -> i32 { doc_as_u32(d) as i32 }
 315     pub fn doc_as_i64(d: Doc) -> i64 { doc_as_u64(d) as i64 }
 316
 317     pub struct Decoder<'a> {
 318         parent: Doc<'a>,
 319         pos: uint,
 320     }
 321
 322     impl<'doc> Decoder<'doc> {
 323         pub fn new(d: Doc<'doc>) -> Decoder<'doc> {
 324             Decoder {
 325                 parent: d,
 326                 pos: d.start
 327             }
 328         }
 329
 330         fn _check_label(&mut self, lbl: &str) -> DecodeResult<()> {
 331             if self.pos < self.parent.end {
 332                 let TaggedDoc { tag: r_tag, doc: r_doc } =
 333                     try!(doc_at(self.parent.data, self.pos));
 334
 335                 if r_tag == (EsLabel as uint) {
 336                     self.pos = r_doc.end;
 337                     let str = r_doc.as_str_slice();
 338                     if lbl != str {
 339                         return Err(Expected(format!("Expected label {} but \
 340                                                      found {}", lbl, str)));
 341                     }
 342                 }
 343             }
 344             Ok(())
 345         }
 346
 347         fn next_doc(&mut self, exp_tag: EbmlEncoderTag) -> DecodeResult<Doc<'doc>> {
 348             debug!(". next_doc(exp_tag={})", exp_tag);
 349             if self.pos >= self.parent.end {
 350                 return Err(Expected(format!("no more documents in \
 351                                              current node!")));
 352             }
 353             let TaggedDoc { tag: r_tag, doc: r_doc } =
 354                 try!(doc_at(self.parent.data, self.pos));
 355             debug!("self.parent={}-{} self.pos={} r_tag={} r_doc={}-{}",
 356                    self.parent.start,
 357                    self.parent.end,
 358                    self.pos,
 359                    r_tag,
 360                    r_doc.start,
 361                    r_doc.end);
 362             if r_tag != (exp_tag as uint) {
 363                 return Err(Expected(format!("expected EBML doc with tag {} but \
 364                                              found tag {}", exp_tag, r_tag)));
 365             }
 366             if r_doc.end > self.parent.end {
 367                 return Err(Expected(format!("invalid EBML, child extends to \
 368                                              {:#x}, parent to {:#x}",
 369                                             r_doc.end, self.parent.end)));
 370             }
 371             self.pos = r_doc.end;
 372             Ok(r_doc)
 373         }
 374
 375         fn push_doc<T>(&mut self, exp_tag: EbmlEncoderTag,
 376                        f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 377             let d = try!(self.next_doc(exp_tag));
 378             let old_parent = self.parent;
 379             let old_pos = self.pos;
 380             self.parent = d;
 381             self.pos = d.start;
 382             let r = try!(f(self));
 383             self.parent = old_parent;
 384             self.pos = old_pos;
 385             Ok(r)
 386         }
 387
 388         fn _next_uint(&mut self, exp_tag: EbmlEncoderTag) -> DecodeResult<uint> {
 389             let r = doc_as_u32(try!(self.next_doc(exp_tag)));
 390             debug!("_next_uint exp_tag={} result={}", exp_tag, r);
 391             Ok(r as uint)
 392         }
 393
 394         pub fn read_opaque<R>(&mut self,
 395                               op: |&mut Decoder<'doc>, Doc| -> DecodeResult<R>) -> DecodeResult<R> {
 396             let doc = try!(self.next_doc(EsOpaque));
 397
 398             let (old_parent, old_pos) = (self.parent, self.pos);
 399             self.parent = doc;
 400             self.pos = doc.start;
 401
 402             let result = try!(op(self, doc));
 403
 404             self.parent = old_parent;
 405             self.pos = old_pos;
 406             Ok(result)
 407         }
 408     }
 409
 410     impl<'doc> serialize::Decoder<Error> for Decoder<'doc> {
 411         fn read_nil(&mut self) -> DecodeResult<()> { Ok(()) }
 412
 413         fn read_u64(&mut self) -> DecodeResult<u64> { Ok(doc_as_u64(try!(self.next_doc(EsU64)))) }
 414         fn read_u32(&mut self) -> DecodeResult<u32> { Ok(doc_as_u32(try!(self.next_doc(EsU32)))) }
 415         fn read_u16(&mut self) -> DecodeResult<u16> { Ok(doc_as_u16(try!(self.next_doc(EsU16)))) }
 416         fn read_u8 (&mut self) -> DecodeResult<u8 > { Ok(doc_as_u8 (try!(self.next_doc(EsU8 )))) }
 417         fn read_uint(&mut self) -> DecodeResult<uint> {
 418             let v = doc_as_u64(try!(self.next_doc(EsUint)));
 419             if v > (::std::uint::MAX as u64) {
 420                 Err(IntTooBig(v as uint))
 421             } else {
 422                 Ok(v as uint)
 423             }
 424         }
 425
 426         fn read_i64(&mut self) -> DecodeResult<i64> {
 427             Ok(doc_as_u64(try!(self.next_doc(EsI64))) as i64)
 428         }
 429         fn read_i32(&mut self) -> DecodeResult<i32> {
 430             Ok(doc_as_u32(try!(self.next_doc(EsI32))) as i32)
 431         }
 432         fn read_i16(&mut self) -> DecodeResult<i16> {
 433             Ok(doc_as_u16(try!(self.next_doc(EsI16))) as i16)
 434         }
 435         fn read_i8 (&mut self) -> DecodeResult<i8> {
 436             Ok(doc_as_u8(try!(self.next_doc(EsI8 ))) as i8)
 437         }
 438         fn read_int(&mut self) -> DecodeResult<int> {
 439             let v = doc_as_u64(try!(self.next_doc(EsInt))) as i64;
 440             if v > (int::MAX as i64) || v < (int::MIN as i64) {
 441                 debug!("FIXME \\#6122: Removing this makes this function miscompile");
 442                 Err(IntTooBig(v as uint))
 443             } else {
 444                 Ok(v as int)
 445             }
 446         }
 447
 448         fn read_bool(&mut self) -> DecodeResult<bool> {
 449             Ok(doc_as_u8(try!(self.next_doc(EsBool))) != 0)
 450         }
 451
 452         fn read_f64(&mut self) -> DecodeResult<f64> {
 453             let bits = doc_as_u64(try!(self.next_doc(EsF64)));
 454             Ok(unsafe { transmute(bits) })
 455         }
 456         fn read_f32(&mut self) -> DecodeResult<f32> {
 457             let bits = doc_as_u32(try!(self.next_doc(EsF32)));
 458             Ok(unsafe { transmute(bits) })
 459         }
 460         fn read_char(&mut self) -> DecodeResult<char> {
 461             Ok(char::from_u32(doc_as_u32(try!(self.next_doc(EsChar)))).unwrap())
 462         }
 463         fn read_str(&mut self) -> DecodeResult<String> {
 464             Ok(try!(self.next_doc(EsStr)).as_str())
 465         }
 466
 467         // Compound types:
 468         fn read_enum<T>(&mut self,
 469                         name: &str,
 470                         f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 471             debug!("read_enum({})", name);
 472             try!(self._check_label(name));
 473
 474             let doc = try!(self.next_doc(EsEnum));
 475
 476             let (old_parent, old_pos) = (self.parent, self.pos);
 477             self.parent = doc;
 478             self.pos = self.parent.start;
 479
 480             let result = try!(f(self));
 481
 482             self.parent = old_parent;
 483             self.pos = old_pos;
 484             Ok(result)
 485         }
 486
 487         fn read_enum_variant<T>(&mut self,
 488                                 _: &[&str],
 489                                 f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>)
 490                                 -> DecodeResult<T> {
 491             debug!("read_enum_variant()");
 492             let idx = try!(self._next_uint(EsEnumVid));
 493             debug!("  idx={}", idx);
 494
 495             let doc = try!(self.next_doc(EsEnumBody));
 496
 497             let (old_parent, old_pos) = (self.parent, self.pos);
 498             self.parent = doc;
 499             self.pos = self.parent.start;
 500
 501             let result = try!(f(self, idx));
 502
 503             self.parent = old_parent;
 504             self.pos = old_pos;
 505             Ok(result)
 506         }
 507
 508         fn read_enum_variant_arg<T>(&mut self,
 509                                     idx: uint,
 510                                     f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 511             debug!("read_enum_variant_arg(idx={})", idx);
 512             f(self)
 513         }
 514
 515         fn read_enum_struct_variant<T>(&mut self,
 516                                        _: &[&str],
 517                                        f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>)
 518                                        -> DecodeResult<T> {
 519             debug!("read_enum_struct_variant()");
 520             let idx = try!(self._next_uint(EsEnumVid));
 521             debug!("  idx={}", idx);
 522
 523             let doc = try!(self.next_doc(EsEnumBody));
 524
 525             let (old_parent, old_pos) = (self.parent, self.pos);
 526             self.parent = doc;
 527             self.pos = self.parent.start;
 528
 529             let result = try!(f(self, idx));
 530
 531             self.parent = old_parent;
 532             self.pos = old_pos;
 533             Ok(result)
 534         }
 535
 536         fn read_enum_struct_variant_field<T>(&mut self,
 537                                              name: &str,
 538                                              idx: uint,
 539                                              f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 540                                              -> DecodeResult<T> {
 541             debug!("read_enum_struct_variant_arg(name={}, idx={})", name, idx);
 542             f(self)
 543         }
 544
 545         fn read_struct<T>(&mut self,
 546                           name: &str,
 547                           _: uint,
 548                           f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 549                           -> DecodeResult<T> {
 550             debug!("read_struct(name={})", name);
 551             f(self)
 552         }
 553
 554         fn read_struct_field<T>(&mut self,
 555                                 name: &str,
 556                                 idx: uint,
 557                                 f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 558                                 -> DecodeResult<T> {
 559             debug!("read_struct_field(name={}, idx={})", name, idx);
 560             try!(self._check_label(name));
 561             f(self)
 562         }
 563
 564         fn read_tuple<T>(&mut self,
 565                          tuple_len: uint,
 566                          f: |&mut Decoder<'doc>| -> DecodeResult<T>) -> DecodeResult<T> {
 567             debug!("read_tuple()");
 568             self.read_seq(|d, len| {
 569                 if len == tuple_len {
 570                     f(d)
 571                 } else {
 572                     Err(Expected(format!("Expected tuple of length `{}`, \
 573                                           found tuple of length `{}`", tuple_len, len)))
 574                 }
 575             })
 576         }
 577
 578         fn read_tuple_arg<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 579                              -> DecodeResult<T> {
 580             debug!("read_tuple_arg(idx={})", idx);
 581             self.read_seq_elt(idx, f)
 582         }
 583
 584         fn read_tuple_struct<T>(&mut self,
 585                                 name: &str,
 586                                 len: uint,
 587                                 f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 588                                 -> DecodeResult<T> {
 589             debug!("read_tuple_struct(name={})", name);
 590             self.read_tuple(len, f)
 591         }
 592
 593         fn read_tuple_struct_arg<T>(&mut self,
 594                                     idx: uint,
 595                                     f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 596                                     -> DecodeResult<T> {
 597             debug!("read_tuple_struct_arg(idx={})", idx);
 598             self.read_tuple_arg(idx, f)
 599         }
 600
 601         fn read_option<T>(&mut self,
 602                           f: |&mut Decoder<'doc>, bool| -> DecodeResult<T>) -> DecodeResult<T> {
 603             debug!("read_option()");
 604             self.read_enum("Option", |this| {
 605                 this.read_enum_variant(&["None", "Some"], |this, idx| {
 606                     match idx {
 607                         0 => f(this, false),
 608                         1 => f(this, true),
 609                         _ => {
 610                             Err(Expected(format!("Expected None or Some")))
 611                         }
 612                     }
 613                 })
 614             })
 615         }
 616
 617         fn read_seq<T>(&mut self,
 618                        f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>) -> DecodeResult<T> {
 619             debug!("read_seq()");
 620             self.push_doc(EsVec, |d| {
 621                 let len = try!(d._next_uint(EsVecLen));
 622                 debug!("  len={}", len);
 623                 f(d, len)
 624             })
 625         }
 626
 627         fn read_seq_elt<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 628                            -> DecodeResult<T> {
 629             debug!("read_seq_elt(idx={})", idx);
 630             self.push_doc(EsVecElt, f)
 631         }
 632
 633         fn read_map<T>(&mut self,
 634                        f: |&mut Decoder<'doc>, uint| -> DecodeResult<T>) -> DecodeResult<T> {
 635             debug!("read_map()");
 636             self.push_doc(EsMap, |d| {
 637                 let len = try!(d._next_uint(EsMapLen));
 638                 debug!("  len={}", len);
 639                 f(d, len)
 640             })
 641         }
 642
 643         fn read_map_elt_key<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 644                                -> DecodeResult<T> {
 645             debug!("read_map_elt_key(idx={})", idx);
 646             self.push_doc(EsMapKey, f)
 647         }
 648
 649         fn read_map_elt_val<T>(&mut self, idx: uint, f: |&mut Decoder<'doc>| -> DecodeResult<T>)
 650                                -> DecodeResult<T> {
 651             debug!("read_map_elt_val(idx={})", idx);
 652             self.push_doc(EsMapVal, f)
 653         }
 654
 655         fn error(&mut self, err: &str) -> Error {
 656             ApplicationError(err.to_string())
 657         }
 658     }
 659 }
 660
 661 pub mod writer {
 662     use std::clone::Clone;
 663     use std::io::extensions::u64_to_be_bytes;
 664     use std::io::{Writer, Seek};
 665     use std::io;
 666     use std::mem;
 667
 668     use super::{ EsVec, EsMap, EsEnum, EsVecLen, EsVecElt, EsMapLen, EsMapKey,
 669         EsEnumVid, EsU64, EsU32, EsU16, EsU8, EsInt, EsI64, EsI32, EsI16, EsI8,
 670         EsBool, EsF64, EsF32, EsChar, EsStr, EsMapVal, EsEnumBody, EsUint,
 671         EsOpaque, EsLabel, EbmlEncoderTag };
 672
 673     use serialize;
 674
 675
 676     pub type EncodeResult = io::IoResult<()>;
 677
 678     // rbml writing
 679     pub struct Encoder<'a, W:'a> {
 680         pub writer: &'a mut W,
 681         size_positions: Vec<uint>,
 682     }
 683
 684     fn write_sized_vuint<W: Writer>(w: &mut W, n: uint, size: uint) -> EncodeResult {
 685         match size {
 686             1u => w.write(&[0x80u8 | (n as u8)]),
 687             2u => w.write(&[0x40u8 | ((n >> 8_u) as u8), n as u8]),
 688             3u => w.write(&[0x20u8 | ((n >> 16_u) as u8), (n >> 8_u) as u8,
 689                             n as u8]),
 690             4u => w.write(&[0x10u8 | ((n >> 24_u) as u8), (n >> 16_u) as u8,
 691                             (n >> 8_u) as u8, n as u8]),
 692             _ => Err(io::IoError {
 693                 kind: io::OtherIoError,
 694                 desc: "int too big",
 695                 detail: Some(format!("{}", n))
 696             })
 697         }
 698     }
 699
 700     fn write_vuint<W: Writer>(w: &mut W, n: uint) -> EncodeResult {
 701         if n < 0x7f_u { return write_sized_vuint(w, n, 1u); }
 702         if n < 0x4000_u { return write_sized_vuint(w, n, 2u); }
 703         if n < 0x200000_u { return write_sized_vuint(w, n, 3u); }
 704         if n < 0x10000000_u { return write_sized_vuint(w, n, 4u); }
 705         Err(io::IoError {
 706             kind: io::OtherIoError,
 707             desc: "int too big",
 708             detail: Some(format!("{}", n))
 709         })
 710     }
 711
 712     // FIXME (#2741): Provide a function to write the standard rbml header.
 713     impl<'a, W: Writer + Seek> Encoder<'a, W> {
 714         pub fn new(w: &'a mut W) -> Encoder<'a, W> {
 715             Encoder {
 716                 writer: w,
 717                 size_positions: vec!(),
 718             }
 719         }
 720
 721         /// FIXME(pcwalton): Workaround for badness in trans. DO NOT USE ME.
 722         pub unsafe fn unsafe_clone(&self) -> Encoder<'a, W> {
 723             Encoder {
 724                 writer: mem::transmute_copy(&self.writer),
 725                 size_positions: self.size_positions.clone(),
 726             }
 727         }
 728
 729         pub fn start_tag(&mut self, tag_id: uint) -> EncodeResult {
 730             debug!("Start tag {}", tag_id);
 731
 732             // Write the enum ID:
 733             try!(write_vuint(self.writer, tag_id));
 734
 735             // Write a placeholder four-byte size.
 736             self.size_positions.push(try!(self.writer.tell()) as uint);
 737             let zeroes: &[u8] = &[0u8, 0u8, 0u8, 0u8];
 738             self.writer.write(zeroes)
 739         }
 740
 741         pub fn end_tag(&mut self) -> EncodeResult {
 742             let last_size_pos = self.size_positions.pop().unwrap();
 743             let cur_pos = try!(self.writer.tell());
 744             try!(self.writer.seek(last_size_pos as i64, io::SeekSet));
 745             let size = cur_pos as uint - last_size_pos - 4;
 746             try!(write_sized_vuint(self.writer, size, 4u));
 747             let r = try!(self.writer.seek(cur_pos as i64, io::SeekSet));
 748
 749             debug!("End tag (size = {})", size);
 750             Ok(r)
 751         }
 752
 753         pub fn wr_tag(&mut self, tag_id: uint, blk: || -> EncodeResult) -> EncodeResult {
 754             try!(self.start_tag(tag_id));
 755             try!(blk());
 756             self.end_tag()
 757         }
 758
 759         pub fn wr_tagged_bytes(&mut self, tag_id: uint, b: &[u8]) -> EncodeResult {
 760             try!(write_vuint(self.writer, tag_id));
 761             try!(write_vuint(self.writer, b.len()));
 762             self.writer.write(b)
 763         }
 764
 765         pub fn wr_tagged_u64(&mut self, tag_id: uint, v: u64) -> EncodeResult {
 766             u64_to_be_bytes(v, 8u, |v| {
 767                 self.wr_tagged_bytes(tag_id, v)
 768             })
 769         }
 770
 771         pub fn wr_tagged_u32(&mut self, tag_id: uint, v: u32)  -> EncodeResult{
 772             u64_to_be_bytes(v as u64, 4u, |v| {
 773                 self.wr_tagged_bytes(tag_id, v)
 774             })
 775         }
 776
 777         pub fn wr_tagged_u16(&mut self, tag_id: uint, v: u16) -> EncodeResult {
 778             u64_to_be_bytes(v as u64, 2u, |v| {
 779                 self.wr_tagged_bytes(tag_id, v)
 780             })
 781         }
 782
 783         pub fn wr_tagged_u8(&mut self, tag_id: uint, v: u8) -> EncodeResult {
 784             self.wr_tagged_bytes(tag_id, &[v])
 785         }
 786
 787         pub fn wr_tagged_i64(&mut self, tag_id: uint, v: i64) -> EncodeResult {
 788             u64_to_be_bytes(v as u64, 8u, |v| {
 789                 self.wr_tagged_bytes(tag_id, v)
 790             })
 791         }
 792
 793         pub fn wr_tagged_i32(&mut self, tag_id: uint, v: i32) -> EncodeResult {
 794             u64_to_be_bytes(v as u64, 4u, |v| {
 795                 self.wr_tagged_bytes(tag_id, v)
 796             })
 797         }
 798
 799         pub fn wr_tagged_i16(&mut self, tag_id: uint, v: i16) -> EncodeResult {
 800             u64_to_be_bytes(v as u64, 2u, |v| {
 801                 self.wr_tagged_bytes(tag_id, v)
 802             })
 803         }
 804
 805         pub fn wr_tagged_i8(&mut self, tag_id: uint, v: i8) -> EncodeResult {
 806             self.wr_tagged_bytes(tag_id, &[v as u8])
 807         }
 808
 809         pub fn wr_tagged_str(&mut self, tag_id: uint, v: &str) -> EncodeResult {
 810             self.wr_tagged_bytes(tag_id, v.as_bytes())
 811         }
 812
 813         pub fn wr_bytes(&mut self, b: &[u8]) -> EncodeResult {
 814             debug!("Write {} bytes", b.len());
 815             self.writer.write(b)
 816         }
 817
 818         pub fn wr_str(&mut self, s: &str) -> EncodeResult {
 819             debug!("Write str: {}", s);
 820             self.writer.write(s.as_bytes())
 821         }
 822     }
 823
 824     // FIXME (#2743): optionally perform "relaxations" on end_tag to more
 825     // efficiently encode sizes; this is a fixed point iteration
 826
 827     // Set to true to generate more debugging in EBML code.
 828     // Totally lame approach.
 829     static DEBUG: bool = true;
 830
 831     impl<'a, W: Writer + Seek> Encoder<'a, W> {
 832         // used internally to emit things like the vector length and so on
 833         fn _emit_tagged_uint(&mut self, t: EbmlEncoderTag, v: uint) -> EncodeResult {
 834             assert!(v <= 0xFFFF_FFFF_u);
 835             self.wr_tagged_u32(t as uint, v as u32)
 836         }
 837
 838         fn _emit_label(&mut self, label: &str) -> EncodeResult {
 839             // There are various strings that we have access to, such as
 840             // the name of a record field, which do not actually appear in
 841             // the encoded EBML (normally).  This is just for
 842             // efficiency.  When debugging, though, we can emit such
 843             // labels and then they will be checked by decoder to
 844             // try and check panics more quickly.
 845             if DEBUG { self.wr_tagged_str(EsLabel as uint, label) }
 846             else { Ok(()) }
 847         }
 848
 849         pub fn emit_opaque(&mut self, f: |&mut Encoder<W>| -> EncodeResult) -> EncodeResult {
 850             try!(self.start_tag(EsOpaque as uint));
 851             try!(f(self));
 852             self.end_tag()
 853         }
 854     }
 855
 856     impl<'a, W: Writer + Seek> serialize::Encoder<io::IoError> for Encoder<'a, W> {
 857         fn emit_nil(&mut self) -> EncodeResult {
 858             Ok(())
 859         }
 860
 861         fn emit_uint(&mut self, v: uint) -> EncodeResult {
 862             self.wr_tagged_u64(EsUint as uint, v as u64)
 863         }
 864         fn emit_u64(&mut self, v: u64) -> EncodeResult {
 865             self.wr_tagged_u64(EsU64 as uint, v)
 866         }
 867         fn emit_u32(&mut self, v: u32) -> EncodeResult {
 868             self.wr_tagged_u32(EsU32 as uint, v)
 869         }
 870         fn emit_u16(&mut self, v: u16) -> EncodeResult {
 871             self.wr_tagged_u16(EsU16 as uint, v)
 872         }
 873         fn emit_u8(&mut self, v: u8) -> EncodeResult {
 874             self.wr_tagged_u8(EsU8 as uint, v)
 875         }
 876
 877         fn emit_int(&mut self, v: int) -> EncodeResult {
 878             self.wr_tagged_i64(EsInt as uint, v as i64)
 879         }
 880         fn emit_i64(&mut self, v: i64) -> EncodeResult {
 881             self.wr_tagged_i64(EsI64 as uint, v)
 882         }
 883         fn emit_i32(&mut self, v: i32) -> EncodeResult {
 884             self.wr_tagged_i32(EsI32 as uint, v)
 885         }
 886         fn emit_i16(&mut self, v: i16) -> EncodeResult {
 887             self.wr_tagged_i16(EsI16 as uint, v)
 888         }
 889         fn emit_i8(&mut self, v: i8) -> EncodeResult {
 890             self.wr_tagged_i8(EsI8 as uint, v)
 891         }
 892
 893         fn emit_bool(&mut self, v: bool) -> EncodeResult {
 894             self.wr_tagged_u8(EsBool as uint, v as u8)
 895         }
 896
 897         fn emit_f64(&mut self, v: f64) -> EncodeResult {
 898             let bits = unsafe { mem::transmute(v) };
 899             self.wr_tagged_u64(EsF64 as uint, bits)
 900         }
 901         fn emit_f32(&mut self, v: f32) -> EncodeResult {
 902             let bits = unsafe { mem::transmute(v) };
 903             self.wr_tagged_u32(EsF32 as uint, bits)
 904         }
 905         fn emit_char(&mut self, v: char) -> EncodeResult {
 906             self.wr_tagged_u32(EsChar as uint, v as u32)
 907         }
 908
 909         fn emit_str(&mut self, v: &str) -> EncodeResult {
 910             self.wr_tagged_str(EsStr as uint, v)
 911         }
 912
 913         fn emit_enum(&mut self,
 914                      name: &str,
 915                      f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 916             try!(self._emit_label(name));
 917             try!(self.start_tag(EsEnum as uint));
 918             try!(f(self));
 919             self.end_tag()
 920         }
 921
 922         fn emit_enum_variant(&mut self,
 923                              _: &str,
 924                              v_id: uint,
 925                              _: uint,
 926                              f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 927             try!(self._emit_tagged_uint(EsEnumVid, v_id));
 928             try!(self.start_tag(EsEnumBody as uint));
 929             try!(f(self));
 930             self.end_tag()
 931         }
 932
 933         fn emit_enum_variant_arg(&mut self,
 934                                  _: uint,
 935                                  f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 936             f(self)
 937         }
 938
 939         fn emit_enum_struct_variant(&mut self,
 940                                     v_name: &str,
 941                                     v_id: uint,
 942                                     cnt: uint,
 943                                     f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 944             self.emit_enum_variant(v_name, v_id, cnt, f)
 945         }
 946
 947         fn emit_enum_struct_variant_field(&mut self,
 948                                           _: &str,
 949                                           idx: uint,
 950                                           f: |&mut Encoder<'a, W>| -> EncodeResult)
 951             -> EncodeResult {
 952             self.emit_enum_variant_arg(idx, f)
 953         }
 954
 955         fn emit_struct(&mut self,
 956                        _: &str,
 957                        _len: uint,
 958                        f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 959             f(self)
 960         }
 961
 962         fn emit_struct_field(&mut self,
 963                              name: &str,
 964                              _: uint,
 965                              f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 966             try!(self._emit_label(name));
 967             f(self)
 968         }
 969
 970         fn emit_tuple(&mut self,
 971                       len: uint,
 972                       f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 973             self.emit_seq(len, f)
 974         }
 975         fn emit_tuple_arg(&mut self,
 976                           idx: uint,
 977                           f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 978             self.emit_seq_elt(idx, f)
 979         }
 980
 981         fn emit_tuple_struct(&mut self,
 982                              _: &str,
 983                              len: uint,
 984                              f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 985             self.emit_seq(len, f)
 986         }
 987         fn emit_tuple_struct_arg(&mut self,
 988                                  idx: uint,
 989                                  f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 990             self.emit_seq_elt(idx, f)
 991         }
 992
 993         fn emit_option(&mut self,
 994                        f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
 995             self.emit_enum("Option", f)
 996         }
 997         fn emit_option_none(&mut self) -> EncodeResult {
 998             self.emit_enum_variant("None", 0, 0, |_| Ok(()))
 999         }
1000         fn emit_option_some(&mut self,
1001                             f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1002
1003             self.emit_enum_variant("Some", 1, 1, f)
1004         }
1005
1006         fn emit_seq(&mut self,
1007                     len: uint,
1008                     f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1009
1010             try!(self.start_tag(EsVec as uint));
1011             try!(self._emit_tagged_uint(EsVecLen, len));
1012             try!(f(self));
1013             self.end_tag()
1014         }
1015
1016         fn emit_seq_elt(&mut self,
1017                         _idx: uint,
1018                         f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1019
1020             try!(self.start_tag(EsVecElt as uint));
1021             try!(f(self));
1022             self.end_tag()
1023         }
1024
1025         fn emit_map(&mut self,
1026                     len: uint,
1027                     f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1028
1029             try!(self.start_tag(EsMap as uint));
1030             try!(self._emit_tagged_uint(EsMapLen, len));
1031             try!(f(self));
1032             self.end_tag()
1033         }
1034
1035         fn emit_map_elt_key(&mut self,
1036                             _idx: uint,
1037                             f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1038
1039             try!(self.start_tag(EsMapKey as uint));
1040             try!(f(self));
1041             self.end_tag()
1042         }
1043
1044         fn emit_map_elt_val(&mut self,
1045                             _idx: uint,
1046                             f: |&mut Encoder<'a, W>| -> EncodeResult) -> EncodeResult {
1047             try!(self.start_tag(EsMapVal as uint));
1048             try!(f(self));
1049             self.end_tag()
1050         }
1051     }
1052 }
1053
1054 // ___________________________________________________________________________
1055 // Testing
1056
1057 #[cfg(test)]
1058 mod tests {
1059     use super::{Doc, reader, writer};
1060     use super::io::SeekableMemWriter;
1061
1062     use serialize::{Encodable, Decodable};
1063
1064     use std::option::Option;
1065     use std::option::Option::{None, Some};
1066
1067     #[test]
1068     fn test_vuint_at() {
1069         let data = &[
1070             0x80,
1071             0xff,
1072             0x40, 0x00,
1073             0x7f, 0xff,
1074             0x20, 0x00, 0x00,
1075             0x3f, 0xff, 0xff,
1076             0x10, 0x00, 0x00, 0x00,
1077             0x1f, 0xff, 0xff, 0xff
1078         ];
1079
1080         let mut res: reader::Res;
1081
1082         // Class A
1083         res = reader::vuint_at(data, 0).unwrap();
1084         assert_eq!(res.val, 0);
1085         assert_eq!(res.next, 1);
1086         res = reader::vuint_at(data, res.next).unwrap();
1087         assert_eq!(res.val, (1 << 7) - 1);
1088         assert_eq!(res.next, 2);
1089
1090         // Class B
1091         res = reader::vuint_at(data, res.next).unwrap();
1092         assert_eq!(res.val, 0);
1093         assert_eq!(res.next, 4);
1094         res = reader::vuint_at(data, res.next).unwrap();
1095         assert_eq!(res.val, (1 << 14) - 1);
1096         assert_eq!(res.next, 6);
1097
1098         // Class C
1099         res = reader::vuint_at(data, res.next).unwrap();
1100         assert_eq!(res.val, 0);
1101         assert_eq!(res.next, 9);
1102         res = reader::vuint_at(data, res.next).unwrap();
1103         assert_eq!(res.val, (1 << 21) - 1);
1104         assert_eq!(res.next, 12);
1105
1106         // Class D
1107         res = reader::vuint_at(data, res.next).unwrap();
1108         assert_eq!(res.val, 0);
1109         assert_eq!(res.next, 16);
1110         res = reader::vuint_at(data, res.next).unwrap();
1111         assert_eq!(res.val, (1 << 28) - 1);
1112         assert_eq!(res.next, 20);
1113     }
1114
1115     #[test]
1116     fn test_option_int() {
1117         fn test_v(v: Option<int>) {
1118             debug!("v == {}", v);
1119             let mut wr = SeekableMemWriter::new();
1120             {
1121                 let mut rbml_w = writer::Encoder::new(&mut wr);
1122                 let _ = v.encode(&mut rbml_w);
1123             }
1124             let rbml_doc = Doc::new(wr.get_ref());
1125             let mut deser = reader::Decoder::new(rbml_doc);
1126             let v1 = Decodable::decode(&mut deser).unwrap();
1127             debug!("v1 == {}", v1);
1128             assert_eq!(v, v1);
1129         }
1130
1131         test_v(Some(22));
1132         test_v(None);
1133         test_v(Some(3));
1134     }
1135 }
1136
1137 #[cfg(test)]
1138 mod bench {
1139     #![allow(non_snake_case)]
1140     use test::Bencher;
1141     use super::reader;
1142
1143     #[bench]
1144     pub fn vuint_at_A_aligned(b: &mut Bencher) {
1145         let data = Vec::from_fn(4*100, |i| {
1146             match i % 2 {
1147               0 => 0x80u8,
1148               _ => i as u8,
1149             }
1150         });
1151         let mut sum = 0u;
1152         b.iter(|| {
1153             let mut i = 0;
1154             while i < data.len() {
1155                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1156                 i += 4;
1157             }
1158         });
1159     }
1160
1161     #[bench]
1162     pub fn vuint_at_A_unaligned(b: &mut Bencher) {
1163         let data = Vec::from_fn(4*100+1, |i| {
1164             match i % 2 {
1165               1 => 0x80u8,
1166               _ => i as u8
1167             }
1168         });
1169         let mut sum = 0u;
1170         b.iter(|| {
1171             let mut i = 1;
1172             while i < data.len() {
1173                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1174                 i += 4;
1175             }
1176         });
1177     }
1178
1179     #[bench]
1180     pub fn vuint_at_D_aligned(b: &mut Bencher) {
1181         let data = Vec::from_fn(4*100, |i| {
1182             match i % 4 {
1183               0 => 0x10u8,
1184               3 => i as u8,
1185               _ => 0u8
1186             }
1187         });
1188         let mut sum = 0u;
1189         b.iter(|| {
1190             let mut i = 0;
1191             while i < data.len() {
1192                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1193                 i += 4;
1194             }
1195         });
1196     }
1197
1198     #[bench]
1199     pub fn vuint_at_D_unaligned(b: &mut Bencher) {
1200         let data = Vec::from_fn(4*100+1, |i| {
1201             match i % 4 {
1202               1 => 0x10u8,
1203               0 => i as u8,
1204               _ => 0u8
1205             }
1206         });
1207         let mut sum = 0u;
1208         b.iter(|| {
1209             let mut i = 1;
1210             while i < data.len() {
1211                 sum += reader::vuint_at(data.as_slice(), i).unwrap().val;
1212                 i += 4;
1213             }
1214         });
1215     }
1216 }