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