src/libserialize/json.rs

   1 // Copyright 2012-2013 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 // Rust JSON serialization library
  12 // Copyright (c) 2011 Google Inc.
  13
  14 #![forbid(non_camel_case_types)]
  15 #![allow(missing_doc)]
  16
  17 /*!
  18 JSON parsing and serialization
  19
  20 # What is JSON?
  21
  22 JSON (JavaScript Object Notation) is a way to write data in Javascript.
  23 Like XML it allows one to encode structured data in a text format that can be read by humans easily.
  24 Its native compatibility with JavaScript and its simple syntax make it used widely.
  25
  26 Json data are encoded in a form of "key":"value".
  27 Data types that can be encoded are JavaScript types :
  28 boolean (`true` or `false`), number (`f64`), string, array, object, null.
  29 An object is a series of string keys mapping to values, in `"key": value` format.
  30 Arrays are enclosed in square brackets ([ ... ]) and objects in curly brackets ({ ... }).
  31 A simple JSON document encoding a person, his/her age, address and phone numbers could look like:
  32
  33 ```ignore
  34 {
  35     "FirstName": "John",
  36     "LastName": "Doe",
  37     "Age": 43,
  38     "Address": {
  39         "Street": "Downing Street 10",
  40         "City": "London",
  41         "Country": "Great Britain"
  42     },
  43     "PhoneNumbers": [
  44         "+44 1234567",
  45         "+44 2345678"
  46     ]
  47 }
  48 ```
  49
  50 # Rust Type-based Encoding and Decoding
  51
  52 Rust provides a mechanism for low boilerplate encoding & decoding
  53 of values to and from JSON via the serialization API.
  54 To be able to encode a piece of data, it must implement the `serialize::Encodable` trait.
  55 To be able to decode a piece of data, it must implement the `serialize::Decodable` trait.
  56 The Rust compiler provides an annotation to automatically generate
  57 the code for these traits: `#[deriving(Decodable, Encodable)]`
  58
  59 To encode using Encodable :
  60
  61 ```rust
  62 use std::io;
  63 use serialize::{json, Encodable};
  64
  65  #[deriving(Encodable)]
  66  pub struct TestStruct   {
  67     data_str: String,
  68  }
  69
  70 fn main() {
  71     let to_encode_object = TestStruct{data_str:"example of string to encode".to_string()};
  72     let mut m = io::MemWriter::new();
  73     {
  74         let mut encoder = json::Encoder::new(&mut m as &mut std::io::Writer);
  75         match to_encode_object.encode(&mut encoder) {
  76             Ok(()) => (),
  77             Err(e) => fail!("json encoding error: {}", e)
  78         };
  79     }
  80 }
  81 ```
  82
  83 Two wrapper functions are provided to encode a Encodable object
  84 into a string (String) or buffer (~[u8]): `str_encode(&m)` and `buffer_encode(&m)`.
  85
  86 ```rust
  87 use serialize::json;
  88 let to_encode_object = "example of string to encode".to_string();
  89 let encoded_str: String = json::Encoder::str_encode(&to_encode_object);
  90 ```
  91
  92 JSON API provide an enum `json::Json` and a trait `ToJson` to encode object.
  93 The trait `ToJson` encode object into a container `json::Json` and the API provide writer
  94 to encode them into a stream or a string ...
  95
  96 When using `ToJson` the `Encodable` trait implementation is not mandatory.
  97
  98 A basic `ToJson` example using a TreeMap of attribute name / attribute value:
  99
 100
 101 ```rust
 102 extern crate collections;
 103 extern crate serialize;
 104
 105 use serialize::json;
 106 use serialize::json::ToJson;
 107 use collections::TreeMap;
 108
 109 pub struct MyStruct  {
 110     attr1: u8,
 111     attr2: String,
 112 }
 113
 114 impl ToJson for MyStruct {
 115     fn to_json( &self ) -> json::Json {
 116         let mut d = box TreeMap::new();
 117         d.insert("attr1".to_string(), self.attr1.to_json());
 118         d.insert("attr2".to_string(), self.attr2.to_json());
 119         json::Object(d)
 120     }
 121 }
 122
 123 fn main() {
 124     let test2: MyStruct = MyStruct {attr1: 1, attr2:"test".to_string()};
 125     let tjson: json::Json = test2.to_json();
 126     let json_str: String = tjson.to_str().into_string();
 127 }
 128 ```
 129
 130 To decode a JSON string using `Decodable` trait :
 131
 132 ```rust
 133 extern crate serialize;
 134 use serialize::{json, Decodable};
 135
 136 #[deriving(Decodable)]
 137 pub struct MyStruct  {
 138      attr1: u8,
 139      attr2: String,
 140 }
 141
 142 fn main() {
 143     let json_str_to_decode: String =
 144             "{\"attr1\":1,\"attr2\":\"toto\"}".to_string();
 145     let json_object = json::from_str(json_str_to_decode.as_slice());
 146     let mut decoder = json::Decoder::new(json_object.unwrap());
 147     let decoded_object: MyStruct = match Decodable::decode(&mut decoder) {
 148         Ok(v) => v,
 149         Err(e) => fail!("Decoding error: {}", e)
 150     }; // create the final object
 151 }
 152 ```
 153
 154 # Examples of use
 155
 156 ## Using Autoserialization
 157
 158 Create a struct called TestStruct1 and serialize and deserialize it to and from JSON
 159 using the serialization API, using the derived serialization code.
 160
 161 ```rust
 162 extern crate serialize;
 163 use serialize::{json, Encodable, Decodable};
 164
 165  #[deriving(Decodable, Encodable)] //generate Decodable, Encodable impl.
 166  pub struct TestStruct1  {
 167     data_int: u8,
 168     data_str: String,
 169     data_vector: Vec<u8>,
 170  }
 171
 172 // To serialize use the `json::str_encode` to encode an object in a string.
 173 // It calls the generated `Encodable` impl.
 174 fn main() {
 175     let to_encode_object = TestStruct1
 176          {data_int: 1, data_str:"toto".to_string(), data_vector:vec![2,3,4,5]};
 177     let encoded_str: String = json::Encoder::str_encode(&to_encode_object);
 178
 179     // To deserialize use the `json::from_str` and `json::Decoder`
 180
 181     let json_object = json::from_str(encoded_str.as_slice());
 182     let mut decoder = json::Decoder::new(json_object.unwrap());
 183     let decoded1: TestStruct1 = Decodable::decode(&mut decoder).unwrap(); // create the final object
 184 }
 185 ```
 186
 187 ## Using `ToJson`
 188
 189 This example use the ToJson impl to deserialize the JSON string.
 190 Example of `ToJson` trait implementation for TestStruct1.
 191
 192 ```rust
 193 extern crate serialize;
 194 extern crate collections;
 195
 196 use serialize::json::ToJson;
 197 use serialize::{json, Encodable, Decodable};
 198 use collections::TreeMap;
 199
 200 #[deriving(Decodable, Encodable)] // generate Decodable, Encodable impl.
 201 pub struct TestStruct1  {
 202     data_int: u8,
 203     data_str: String,
 204     data_vector: Vec<u8>,
 205 }
 206
 207 impl ToJson for TestStruct1 {
 208     fn to_json( &self ) -> json::Json {
 209         let mut d = box TreeMap::new();
 210         d.insert("data_int".to_string(), self.data_int.to_json());
 211         d.insert("data_str".to_string(), self.data_str.to_json());
 212         d.insert("data_vector".to_string(), self.data_vector.to_json());
 213         json::Object(d)
 214     }
 215 }
 216
 217 fn main() {
 218     // Serialization using our impl of to_json
 219
 220     let test2: TestStruct1 = TestStruct1 {data_int: 1, data_str:"toto".to_string(),
 221                                           data_vector:vec![2,3,4,5]};
 222     let tjson: json::Json = test2.to_json();
 223     let json_str: String = tjson.to_str().into_string();
 224
 225     // Deserialize like before.
 226
 227     let mut decoder =
 228         json::Decoder::new(json::from_str(json_str.as_slice()).unwrap());
 229     // create the final object
 230     let decoded2: TestStruct1 = Decodable::decode(&mut decoder).unwrap();
 231 }
 232 ```
 233
 234 */
 235
 236 use std::char;
 237 use std::f64;
 238 use std::fmt;
 239 use std::io::MemWriter;
 240 use std::io;
 241 use std::mem::swap;
 242 use std::num;
 243 use std::str::ScalarValue;
 244 use std::str;
 245 use std::string::String;
 246 use std::vec::Vec;
 247
 248 use Encodable;
 249 use collections::{HashMap, TreeMap};
 250
 251 /// Represents a json value
 252 #[deriving(Clone, Eq)]
 253 pub enum Json {
 254     Number(f64),
 255     String(String),
 256     Boolean(bool),
 257     List(List),
 258     Object(Box<Object>),
 259     Null,
 260 }
 261
 262 pub type List = Vec<Json>;
 263 pub type Object = TreeMap<String, Json>;
 264
 265 /// The errors that can arise while parsing a JSON stream.
 266 #[deriving(Clone, Eq)]
 267 pub enum ErrorCode {
 268     InvalidSyntax,
 269     InvalidNumber,
 270     EOFWhileParsingObject,
 271     EOFWhileParsingList,
 272     EOFWhileParsingValue,
 273     EOFWhileParsingString,
 274     KeyMustBeAString,
 275     ExpectedColon,
 276     TrailingCharacters,
 277     InvalidEscape,
 278     InvalidUnicodeCodePoint,
 279     LoneLeadingSurrogateInHexEscape,
 280     UnexpectedEndOfHexEscape,
 281     UnrecognizedHex,
 282     NotFourDigit,
 283     NotUtf8,
 284 }
 285
 286 #[deriving(Clone, Eq, Show)]
 287 pub enum ParserError {
 288     /// msg, line, col
 289     SyntaxError(ErrorCode, uint, uint),
 290     IoError(io::IoErrorKind, &'static str),
 291 }
 292
 293 // Builder and Parser have the same errors.
 294 pub type BuilderError = ParserError;
 295
 296 #[deriving(Clone, Eq, Show)]
 297 pub enum DecoderError {
 298     ParseError(ParserError),
 299     ExpectedError(String, String),
 300     MissingFieldError(String),
 301     UnknownVariantError(String),
 302 }
 303
 304 /// Returns a readable error string for a given error code.
 305 pub fn error_str(error: ErrorCode) -> &'static str {
 306     return match error {
 307         InvalidSyntax => "invalid syntax",
 308         InvalidNumber => "invalid number",
 309         EOFWhileParsingObject => "EOF While parsing object",
 310         EOFWhileParsingList => "EOF While parsing list",
 311         EOFWhileParsingValue => "EOF While parsing value",
 312         EOFWhileParsingString => "EOF While parsing string",
 313         KeyMustBeAString => "key must be a string",
 314         ExpectedColon => "expected `:`",
 315         TrailingCharacters => "trailing characters",
 316         InvalidEscape => "invalid escape",
 317         UnrecognizedHex => "invalid \\u escape (unrecognized hex)",
 318         NotFourDigit => "invalid \\u escape (not four digits)",
 319         NotUtf8 => "contents not utf-8",
 320         InvalidUnicodeCodePoint => "invalid unicode code point",
 321         LoneLeadingSurrogateInHexEscape => "lone leading surrogate in hex escape",
 322         UnexpectedEndOfHexEscape => "unexpected end of hex escape",
 323     }
 324 }
 325
 326 impl fmt::Show for ErrorCode {
 327     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 328         error_str(*self).fmt(f)
 329     }
 330 }
 331
 332
 333 fn io_error_to_error(io: io::IoError) -> ParserError {
 334     IoError(io.kind, io.desc)
 335 }
 336
 337 pub type EncodeResult = io::IoResult<()>;
 338 pub type DecodeResult<T> = Result<T, DecoderError>;
 339
 340 fn escape_str(s: &str) -> String {
 341     let mut escaped = String::from_str("\"");
 342     for c in s.chars() {
 343         match c {
 344             '"' => escaped.push_str("\\\""),
 345             '\\' => escaped.push_str("\\\\"),
 346             '\x08' => escaped.push_str("\\b"),
 347             '\x0c' => escaped.push_str("\\f"),
 348             '\n' => escaped.push_str("\\n"),
 349             '\r' => escaped.push_str("\\r"),
 350             '\t' => escaped.push_str("\\t"),
 351             _ => escaped.push_char(c),
 352         }
 353     };
 354     escaped.push_char('"');
 355     escaped
 356 }
 357
 358 fn spaces(n: uint) -> String {
 359     let mut ss = String::new();
 360     for _ in range(0, n) {
 361         ss.push_str(" ");
 362     }
 363     return ss
 364 }
 365
 366 /// A structure for implementing serialization to JSON.
 367 pub struct Encoder<'a> {
 368     wr: &'a mut io::Writer,
 369 }
 370
 371 impl<'a> Encoder<'a> {
 372     /// Creates a new JSON encoder whose output will be written to the writer
 373     /// specified.
 374     pub fn new<'a>(wr: &'a mut io::Writer) -> Encoder<'a> {
 375         Encoder { wr: wr }
 376     }
 377
 378     /// Encode the specified struct into a json [u8]
 379     pub fn buffer_encode<T:Encodable<Encoder<'a>, io::IoError>>(to_encode_object: &T) -> Vec<u8>  {
 380        //Serialize the object in a string using a writer
 381         let mut m = MemWriter::new();
 382         {
 383             let mut encoder = Encoder::new(&mut m as &mut io::Writer);
 384             // MemWriter never Errs
 385             let _ = to_encode_object.encode(&mut encoder);
 386         }
 387         m.unwrap()
 388     }
 389
 390     /// Encode the specified struct into a json str
 391     pub fn str_encode<T:Encodable<Encoder<'a>,
 392                         io::IoError>>(
 393                       to_encode_object: &T)
 394                       -> String {
 395         let buff = Encoder::buffer_encode(to_encode_object);
 396         str::from_utf8(buff.as_slice()).unwrap().to_string()
 397     }
 398 }
 399
 400 impl<'a> ::Encoder<io::IoError> for Encoder<'a> {
 401     fn emit_nil(&mut self) -> EncodeResult { write!(self.wr, "null") }
 402
 403     fn emit_uint(&mut self, v: uint) -> EncodeResult { self.emit_f64(v as f64) }
 404     fn emit_u64(&mut self, v: u64) -> EncodeResult { self.emit_f64(v as f64) }
 405     fn emit_u32(&mut self, v: u32) -> EncodeResult { self.emit_f64(v as f64) }
 406     fn emit_u16(&mut self, v: u16) -> EncodeResult { self.emit_f64(v as f64) }
 407     fn emit_u8(&mut self, v: u8) -> EncodeResult  { self.emit_f64(v as f64) }
 408
 409     fn emit_int(&mut self, v: int) -> EncodeResult { self.emit_f64(v as f64) }
 410     fn emit_i64(&mut self, v: i64) -> EncodeResult { self.emit_f64(v as f64) }
 411     fn emit_i32(&mut self, v: i32) -> EncodeResult { self.emit_f64(v as f64) }
 412     fn emit_i16(&mut self, v: i16) -> EncodeResult { self.emit_f64(v as f64) }
 413     fn emit_i8(&mut self, v: i8) -> EncodeResult  { self.emit_f64(v as f64) }
 414
 415     fn emit_bool(&mut self, v: bool) -> EncodeResult {
 416         if v {
 417             write!(self.wr, "true")
 418         } else {
 419             write!(self.wr, "false")
 420         }
 421     }
 422
 423     fn emit_f64(&mut self, v: f64) -> EncodeResult {
 424         write!(self.wr, "{}", f64::to_str_digits(v, 6u))
 425     }
 426     fn emit_f32(&mut self, v: f32) -> EncodeResult { self.emit_f64(v as f64) }
 427
 428     fn emit_char(&mut self, v: char) -> EncodeResult {
 429         self.emit_str(str::from_char(v).as_slice())
 430     }
 431     fn emit_str(&mut self, v: &str) -> EncodeResult {
 432         write!(self.wr, "{}", escape_str(v))
 433     }
 434
 435     fn emit_enum(&mut self,
 436                  _name: &str,
 437                  f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult { f(self) }
 438
 439     fn emit_enum_variant(&mut self,
 440                          name: &str,
 441                          _id: uint,
 442                          cnt: uint,
 443                          f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 444         // enums are encoded as strings or objects
 445         // Bunny => "Bunny"
 446         // Kangaroo(34,"William") => {"variant": "Kangaroo", "fields": [34,"William"]}
 447         if cnt == 0 {
 448             write!(self.wr, "{}", escape_str(name))
 449         } else {
 450             try!(write!(self.wr, "\\{\"variant\":"));
 451             try!(write!(self.wr, "{}", escape_str(name)));
 452             try!(write!(self.wr, ",\"fields\":["));
 453             try!(f(self));
 454             write!(self.wr, "]\\}")
 455         }
 456     }
 457
 458     fn emit_enum_variant_arg(&mut self,
 459                              idx: uint,
 460                              f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 461         if idx != 0 {
 462             try!(write!(self.wr, ","));
 463         }
 464         f(self)
 465     }
 466
 467     fn emit_enum_struct_variant(&mut self,
 468                                 name: &str,
 469                                 id: uint,
 470                                 cnt: uint,
 471                                 f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 472         self.emit_enum_variant(name, id, cnt, f)
 473     }
 474
 475     fn emit_enum_struct_variant_field(&mut self,
 476                                       _: &str,
 477                                       idx: uint,
 478                                       f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 479         self.emit_enum_variant_arg(idx, f)
 480     }
 481
 482     fn emit_struct(&mut self,
 483                    _: &str,
 484                    _: uint,
 485                    f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 486         try!(write!(self.wr, r"\{"));
 487         try!(f(self));
 488         write!(self.wr, r"\}")
 489     }
 490
 491     fn emit_struct_field(&mut self,
 492                          name: &str,
 493                          idx: uint,
 494                          f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 495         if idx != 0 { try!(write!(self.wr, ",")); }
 496         try!(write!(self.wr, "{}:", escape_str(name)));
 497         f(self)
 498     }
 499
 500     fn emit_tuple(&mut self, len: uint, f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 501         self.emit_seq(len, f)
 502     }
 503     fn emit_tuple_arg(&mut self,
 504                       idx: uint,
 505                       f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 506         self.emit_seq_elt(idx, f)
 507     }
 508
 509     fn emit_tuple_struct(&mut self,
 510                          _name: &str,
 511                          len: uint,
 512                          f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 513         self.emit_seq(len, f)
 514     }
 515     fn emit_tuple_struct_arg(&mut self,
 516                              idx: uint,
 517                              f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 518         self.emit_seq_elt(idx, f)
 519     }
 520
 521     fn emit_option(&mut self, f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 522         f(self)
 523     }
 524     fn emit_option_none(&mut self) -> EncodeResult { self.emit_nil() }
 525     fn emit_option_some(&mut self, f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 526         f(self)
 527     }
 528
 529     fn emit_seq(&mut self, _len: uint, f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 530         try!(write!(self.wr, "["));
 531         try!(f(self));
 532         write!(self.wr, "]")
 533     }
 534
 535     fn emit_seq_elt(&mut self, idx: uint, f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 536         if idx != 0 {
 537             try!(write!(self.wr, ","));
 538         }
 539         f(self)
 540     }
 541
 542     fn emit_map(&mut self, _len: uint, f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 543         try!(write!(self.wr, r"\{"));
 544         try!(f(self));
 545         write!(self.wr, r"\}")
 546     }
 547
 548     fn emit_map_elt_key(&mut self,
 549                         idx: uint,
 550                         f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 551         use std::str::from_utf8;
 552         if idx != 0 { try!(write!(self.wr, ",")) }
 553         // ref #12967, make sure to wrap a key in double quotes,
 554         // in the event that its of a type that omits them (eg numbers)
 555         let mut buf = MemWriter::new();
 556         let mut check_encoder = Encoder::new(&mut buf);
 557         try!(f(&mut check_encoder));
 558         let buf = buf.unwrap();
 559         let out = from_utf8(buf.as_slice()).unwrap();
 560         let needs_wrapping = out.char_at(0) != '"' &&
 561             out.char_at_reverse(out.len()) != '"';
 562         if needs_wrapping { try!(write!(self.wr, "\"")); }
 563         try!(f(self));
 564         if needs_wrapping { try!(write!(self.wr, "\"")); }
 565         Ok(())
 566     }
 567
 568     fn emit_map_elt_val(&mut self,
 569                         _idx: uint,
 570                         f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
 571         try!(write!(self.wr, ":"));
 572         f(self)
 573     }
 574 }
 575
 576 /// Another encoder for JSON, but prints out human-readable JSON instead of
 577 /// compact data
 578 pub struct PrettyEncoder<'a> {
 579     wr: &'a mut io::Writer,
 580     indent: uint,
 581 }
 582
 583 impl<'a> PrettyEncoder<'a> {
 584     /// Creates a new encoder whose output will be written to the specified writer
 585     pub fn new<'a>(wr: &'a mut io::Writer) -> PrettyEncoder<'a> {
 586         PrettyEncoder {
 587             wr: wr,
 588             indent: 0,
 589         }
 590     }
 591 }
 592
 593 impl<'a> ::Encoder<io::IoError> for PrettyEncoder<'a> {
 594     fn emit_nil(&mut self) -> EncodeResult { write!(self.wr, "null") }
 595
 596     fn emit_uint(&mut self, v: uint) -> EncodeResult { self.emit_f64(v as f64) }
 597     fn emit_u64(&mut self, v: u64) -> EncodeResult { self.emit_f64(v as f64) }
 598     fn emit_u32(&mut self, v: u32) -> EncodeResult { self.emit_f64(v as f64) }
 599     fn emit_u16(&mut self, v: u16) -> EncodeResult { self.emit_f64(v as f64) }
 600     fn emit_u8(&mut self, v: u8) -> EncodeResult { self.emit_f64(v as f64) }
 601
 602     fn emit_int(&mut self, v: int) -> EncodeResult { self.emit_f64(v as f64) }
 603     fn emit_i64(&mut self, v: i64) -> EncodeResult { self.emit_f64(v as f64) }
 604     fn emit_i32(&mut self, v: i32) -> EncodeResult { self.emit_f64(v as f64) }
 605     fn emit_i16(&mut self, v: i16) -> EncodeResult { self.emit_f64(v as f64) }
 606     fn emit_i8(&mut self, v: i8) -> EncodeResult { self.emit_f64(v as f64) }
 607
 608     fn emit_bool(&mut self, v: bool) -> EncodeResult {
 609         if v {
 610             write!(self.wr, "true")
 611         } else {
 612             write!(self.wr, "false")
 613         }
 614     }
 615
 616     fn emit_f64(&mut self, v: f64) -> EncodeResult {
 617         write!(self.wr, "{}", f64::to_str_digits(v, 6u))
 618     }
 619     fn emit_f32(&mut self, v: f32) -> EncodeResult {
 620         self.emit_f64(v as f64)
 621     }
 622
 623     fn emit_char(&mut self, v: char) -> EncodeResult {
 624         self.emit_str(str::from_char(v).as_slice())
 625     }
 626     fn emit_str(&mut self, v: &str) -> EncodeResult {
 627         write!(self.wr, "{}", escape_str(v))
 628     }
 629
 630     fn emit_enum(&mut self,
 631                  _name: &str,
 632                  f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 633         f(self)
 634     }
 635
 636     fn emit_enum_variant(&mut self,
 637                          name: &str,
 638                          _: uint,
 639                          cnt: uint,
 640                          f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 641         if cnt == 0 {
 642             write!(self.wr, "{}", escape_str(name))
 643         } else {
 644             self.indent += 2;
 645             try!(write!(self.wr, "[\n{}{},\n", spaces(self.indent),
 646                           escape_str(name)));
 647             try!(f(self));
 648             self.indent -= 2;
 649             write!(self.wr, "\n{}]", spaces(self.indent))
 650         }
 651     }
 652
 653     fn emit_enum_variant_arg(&mut self,
 654                              idx: uint,
 655                              f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 656         if idx != 0 {
 657             try!(write!(self.wr, ",\n"));
 658         }
 659         try!(write!(self.wr, "{}", spaces(self.indent)));
 660         f(self)
 661     }
 662
 663     fn emit_enum_struct_variant(&mut self,
 664                                 name: &str,
 665                                 id: uint,
 666                                 cnt: uint,
 667                                 f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 668         self.emit_enum_variant(name, id, cnt, f)
 669     }
 670
 671     fn emit_enum_struct_variant_field(&mut self,
 672                                       _: &str,
 673                                       idx: uint,
 674                                       f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 675         self.emit_enum_variant_arg(idx, f)
 676     }
 677
 678
 679     fn emit_struct(&mut self,
 680                    _: &str,
 681                    len: uint,
 682                    f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 683         if len == 0 {
 684             write!(self.wr, "\\{\\}")
 685         } else {
 686             try!(write!(self.wr, "\\{"));
 687             self.indent += 2;
 688             try!(f(self));
 689             self.indent -= 2;
 690             write!(self.wr, "\n{}\\}", spaces(self.indent))
 691         }
 692     }
 693
 694     fn emit_struct_field(&mut self,
 695                          name: &str,
 696                          idx: uint,
 697                          f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 698         if idx == 0 {
 699             try!(write!(self.wr, "\n"));
 700         } else {
 701             try!(write!(self.wr, ",\n"));
 702         }
 703         try!(write!(self.wr, "{}{}: ", spaces(self.indent), escape_str(name)));
 704         f(self)
 705     }
 706
 707     fn emit_tuple(&mut self,
 708                   len: uint,
 709                   f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 710         self.emit_seq(len, f)
 711     }
 712     fn emit_tuple_arg(&mut self,
 713                       idx: uint,
 714                       f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 715         self.emit_seq_elt(idx, f)
 716     }
 717
 718     fn emit_tuple_struct(&mut self,
 719                          _: &str,
 720                          len: uint,
 721                          f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 722         self.emit_seq(len, f)
 723     }
 724     fn emit_tuple_struct_arg(&mut self,
 725                              idx: uint,
 726                              f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 727         self.emit_seq_elt(idx, f)
 728     }
 729
 730     fn emit_option(&mut self, f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 731         f(self)
 732     }
 733     fn emit_option_none(&mut self) -> EncodeResult { self.emit_nil() }
 734     fn emit_option_some(&mut self, f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 735         f(self)
 736     }
 737
 738     fn emit_seq(&mut self,
 739                 len: uint,
 740                 f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 741         if len == 0 {
 742             write!(self.wr, "[]")
 743         } else {
 744             try!(write!(self.wr, "["));
 745             self.indent += 2;
 746             try!(f(self));
 747             self.indent -= 2;
 748             write!(self.wr, "\n{}]", spaces(self.indent))
 749         }
 750     }
 751
 752     fn emit_seq_elt(&mut self,
 753                     idx: uint,
 754                     f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 755         if idx == 0 {
 756             try!(write!(self.wr, "\n"));
 757         } else {
 758             try!(write!(self.wr, ",\n"));
 759         }
 760         try!(write!(self.wr, "{}", spaces(self.indent)));
 761         f(self)
 762     }
 763
 764     fn emit_map(&mut self,
 765                 len: uint,
 766                 f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 767         if len == 0 {
 768             write!(self.wr, "\\{\\}")
 769         } else {
 770             try!(write!(self.wr, "\\{"));
 771             self.indent += 2;
 772             try!(f(self));
 773             self.indent -= 2;
 774             write!(self.wr, "\n{}\\}", spaces(self.indent))
 775         }
 776     }
 777
 778     fn emit_map_elt_key(&mut self,
 779                         idx: uint,
 780                         f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 781         use std::str::from_utf8;
 782         if idx == 0 {
 783             try!(write!(self.wr, "\n"));
 784         } else {
 785             try!(write!(self.wr, ",\n"));
 786         }
 787         try!(write!(self.wr, "{}", spaces(self.indent)));
 788         // ref #12967, make sure to wrap a key in double quotes,
 789         // in the event that its of a type that omits them (eg numbers)
 790         let mut buf = MemWriter::new();
 791         let mut check_encoder = PrettyEncoder::new(&mut buf);
 792         try!(f(&mut check_encoder));
 793         let buf = buf.unwrap();
 794         let out = from_utf8(buf.as_slice()).unwrap();
 795         let needs_wrapping = out.char_at(0) != '"' &&
 796             out.char_at_reverse(out.len()) != '"';
 797         if needs_wrapping { try!(write!(self.wr, "\"")); }
 798         try!(f(self));
 799         if needs_wrapping { try!(write!(self.wr, "\"")); }
 800         Ok(())
 801     }
 802
 803     fn emit_map_elt_val(&mut self,
 804                         _idx: uint,
 805                         f: |&mut PrettyEncoder<'a>| -> EncodeResult) -> EncodeResult {
 806         try!(write!(self.wr, ": "));
 807         f(self)
 808     }
 809 }
 810
 811 impl<E: ::Encoder<S>, S> Encodable<E, S> for Json {
 812     fn encode(&self, e: &mut E) -> Result<(), S> {
 813         match *self {
 814             Number(v) => v.encode(e),
 815             String(ref v) => v.encode(e),
 816             Boolean(v) => v.encode(e),
 817             List(ref v) => v.encode(e),
 818             Object(ref v) => v.encode(e),
 819             Null => e.emit_nil(),
 820         }
 821     }
 822 }
 823
 824 impl Json {
 825     /// Encodes a json value into an io::writer.  Uses a single line.
 826     pub fn to_writer(&self, wr: &mut io::Writer) -> EncodeResult {
 827         let mut encoder = Encoder::new(wr);
 828         self.encode(&mut encoder)
 829     }
 830
 831     /// Encodes a json value into an io::writer.
 832     /// Pretty-prints in a more readable format.
 833     pub fn to_pretty_writer(&self, wr: &mut io::Writer) -> EncodeResult {
 834         let mut encoder = PrettyEncoder::new(wr);
 835         self.encode(&mut encoder)
 836     }
 837
 838     /// Encodes a json value into a string
 839     pub fn to_pretty_str(&self) -> String {
 840         let mut s = MemWriter::new();
 841         self.to_pretty_writer(&mut s as &mut io::Writer).unwrap();
 842         str::from_utf8(s.unwrap().as_slice()).unwrap().to_string()
 843     }
 844
 845      /// If the Json value is an Object, returns the value associated with the provided key.
 846     /// Otherwise, returns None.
 847     pub fn find<'a>(&'a self, key: &String) -> Option<&'a Json>{
 848         match self {
 849             &Object(ref map) => map.find(key),
 850             _ => None
 851         }
 852     }
 853
 854     /// Attempts to get a nested Json Object for each key in `keys`.
 855     /// If any key is found not to exist, find_path will return None.
 856     /// Otherwise, it will return the Json value associated with the final key.
 857     pub fn find_path<'a>(&'a self, keys: &[&String]) -> Option<&'a Json>{
 858         let mut target = self;
 859         for key in keys.iter() {
 860             match target.find(*key) {
 861                 Some(t) => { target = t; },
 862                 None => return None
 863             }
 864         }
 865         Some(target)
 866     }
 867
 868     /// If the Json value is an Object, performs a depth-first search until
 869     /// a value associated with the provided key is found. If no value is found
 870     /// or the Json value is not an Object, returns None.
 871     pub fn search<'a>(&'a self, key: &String) -> Option<&'a Json> {
 872         match self {
 873             &Object(ref map) => {
 874                 match map.find(key) {
 875                     Some(json_value) => Some(json_value),
 876                     None => {
 877                         let mut value : Option<&'a Json> = None;
 878                         for (_, v) in map.iter() {
 879                             value = v.search(key);
 880                             if value.is_some() {
 881                                 break;
 882                             }
 883                         }
 884                         value
 885                     }
 886                 }
 887             },
 888             _ => None
 889         }
 890     }
 891
 892     /// Returns true if the Json value is an Object. Returns false otherwise.
 893     pub fn is_object<'a>(&'a self) -> bool {
 894         self.as_object().is_some()
 895     }
 896
 897     /// If the Json value is an Object, returns the associated TreeMap.
 898     /// Returns None otherwise.
 899     pub fn as_object<'a>(&'a self) -> Option<&'a Object> {
 900         match self {
 901             &Object(ref map) => Some(&**map),
 902             _ => None
 903         }
 904     }
 905
 906     /// Returns true if the Json value is a List. Returns false otherwise.
 907     pub fn is_list<'a>(&'a self) -> bool {
 908         self.as_list().is_some()
 909     }
 910
 911     /// If the Json value is a List, returns the associated vector.
 912     /// Returns None otherwise.
 913     pub fn as_list<'a>(&'a self) -> Option<&'a List> {
 914         match self {
 915             &List(ref list) => Some(&*list),
 916             _ => None
 917         }
 918     }
 919
 920     /// Returns true if the Json value is a String. Returns false otherwise.
 921     pub fn is_string<'a>(&'a self) -> bool {
 922         self.as_string().is_some()
 923     }
 924
 925     /// If the Json value is a String, returns the associated str.
 926     /// Returns None otherwise.
 927     pub fn as_string<'a>(&'a self) -> Option<&'a str> {
 928         match *self {
 929             String(ref s) => Some(s.as_slice()),
 930             _ => None
 931         }
 932     }
 933
 934     /// Returns true if the Json value is a Number. Returns false otherwise.
 935     pub fn is_number(&self) -> bool {
 936         self.as_number().is_some()
 937     }
 938
 939     /// If the Json value is a Number, returns the associated f64.
 940     /// Returns None otherwise.
 941     pub fn as_number(&self) -> Option<f64> {
 942         match self {
 943             &Number(n) => Some(n),
 944             _ => None
 945         }
 946     }
 947
 948     /// Returns true if the Json value is a Boolean. Returns false otherwise.
 949     pub fn is_boolean(&self) -> bool {
 950         self.as_boolean().is_some()
 951     }
 952
 953     /// If the Json value is a Boolean, returns the associated bool.
 954     /// Returns None otherwise.
 955     pub fn as_boolean(&self) -> Option<bool> {
 956         match self {
 957             &Boolean(b) => Some(b),
 958             _ => None
 959         }
 960     }
 961
 962     /// Returns true if the Json value is a Null. Returns false otherwise.
 963     pub fn is_null(&self) -> bool {
 964         self.as_null().is_some()
 965     }
 966
 967     /// If the Json value is a Null, returns ().
 968     /// Returns None otherwise.
 969     pub fn as_null(&self) -> Option<()> {
 970         match self {
 971             &Null => Some(()),
 972             _ => None
 973         }
 974     }
 975 }
 976
 977 /// The output of the streaming parser.
 978 #[deriving(Eq, Clone, Show)]
 979 pub enum JsonEvent {
 980     ObjectStart,
 981     ObjectEnd,
 982     ListStart,
 983     ListEnd,
 984     BooleanValue(bool),
 985     NumberValue(f64),
 986     StringValue(String),
 987     NullValue,
 988     Error(ParserError),
 989 }
 990
 991 #[deriving(Eq, Show)]
 992 enum ParserState {
 993     // Parse a value in a list, true means first element.
 994     ParseList(bool),
 995     // Parse ',' or ']' after an element in a list.
 996     ParseListComma,
 997     // Parse a key:value in an object, true means first element.
 998     ParseObject(bool),
 999     // Parse ',' or ']' after an element in an object.
1000     ParseObjectComma,
1001     // Initialial state.
1002     ParseStart,
1003     // Expecting the stream to end.
1004     ParseBeforeFinish,
1005     // Parsing can't continue.
1006     ParseFinished,
1007 }
1008
1009 /// A Stack represents the current position of the parser in the logical
1010 /// structure of the JSON stream.
1011 /// For example foo.bar[3].x
1012 pub struct Stack {
1013     stack: Vec<InternalStackElement>,
1014     str_buffer: Vec<u8>,
1015 }
1016
1017 /// StackElements compose a Stack.
1018 /// For example, Key("foo"), Key("bar"), Index(3) and Key("x") are the
1019 /// StackElements compositing the stack that represents foo.bar[3].x
1020 #[deriving(Eq, Clone, Show)]
1021 pub enum StackElement<'l> {
1022     Index(u32),
1023     Key(&'l str),
1024 }
1025
1026 // Internally, Key elements are stored as indices in a buffer to avoid
1027 // allocating a string for every member of an object.
1028 #[deriving(Eq, Clone, Show)]
1029 enum InternalStackElement {
1030     InternalIndex(u32),
1031     InternalKey(u16, u16), // start, size
1032 }
1033
1034 impl Stack {
1035     pub fn new() -> Stack {
1036         Stack {
1037             stack: Vec::new(),
1038             str_buffer: Vec::new(),
1039         }
1040     }
1041
1042     /// Returns The number of elements in the Stack.
1043     pub fn len(&self) -> uint { self.stack.len() }
1044
1045     /// Returns true if the stack is empty, equivalent to self.len() == 0.
1046     pub fn is_empty(&self) -> bool { self.stack.len() == 0 }
1047
1048     /// Provides access to the StackElement at a given index.
1049     /// lower indices are at the bottom of the stack while higher indices are
1050     /// at the top.
1051     pub fn get<'l>(&'l self, idx: uint) -> StackElement<'l> {
1052         return match *self.stack.get(idx) {
1053           InternalIndex(i) => { Index(i) }
1054           InternalKey(start, size) => {
1055             Key(str::from_utf8(self.str_buffer.slice(start as uint, (start+size) as uint)).unwrap())
1056           }
1057         }
1058     }
1059
1060     /// Compares this stack with an array of StackElements.
1061     pub fn is_equal_to(&self, rhs: &[StackElement]) -> bool {
1062         if self.stack.len() != rhs.len() { return false; }
1063         for i in range(0, rhs.len()) {
1064             if self.get(i) != rhs[i] { return false; }
1065         }
1066         return true;
1067     }
1068
1069     /// Returns true if the bottom-most elements of this stack are the same as
1070     /// the ones passed as parameter.
1071     pub fn starts_with(&self, rhs: &[StackElement]) -> bool {
1072         if self.stack.len() < rhs.len() { return false; }
1073         for i in range(0, rhs.len()) {
1074             if self.get(i) != rhs[i] { return false; }
1075         }
1076         return true;
1077     }
1078
1079     /// Returns true if the top-most elements of this stack are the same as
1080     /// the ones passed as parameter.
1081     pub fn ends_with(&self, rhs: &[StackElement]) -> bool {
1082         if self.stack.len() < rhs.len() { return false; }
1083         let offset = self.stack.len() - rhs.len();
1084         for i in range(0, rhs.len()) {
1085             if self.get(i + offset) != rhs[i] { return false; }
1086         }
1087         return true;
1088     }
1089
1090     /// Returns the top-most element (if any).
1091     pub fn top<'l>(&'l self) -> Option<StackElement<'l>> {
1092         return match self.stack.last() {
1093             None => None,
1094             Some(&InternalIndex(i)) => Some(Index(i)),
1095             Some(&InternalKey(start, size)) => {
1096                 Some(Key(str::from_utf8(
1097                     self.str_buffer.slice(start as uint, (start+size) as uint)
1098                 ).unwrap()))
1099             }
1100         }
1101     }
1102
1103     // Used by Parser to insert Key elements at the top of the stack.
1104     fn push_key(&mut self, key: String) {
1105         self.stack.push(InternalKey(self.str_buffer.len() as u16, key.len() as u16));
1106         for c in key.as_bytes().iter() {
1107             self.str_buffer.push(*c);
1108         }
1109     }
1110
1111     // Used by Parser to insert Index elements at the top of the stack.
1112     fn push_index(&mut self, index: u32) {
1113         self.stack.push(InternalIndex(index));
1114     }
1115
1116     // Used by Parser to remove the top-most element of the stack.
1117     fn pop(&mut self) {
1118         assert!(!self.is_empty());
1119         match *self.stack.last().unwrap() {
1120             InternalKey(_, sz) => {
1121                 let new_size = self.str_buffer.len() - sz as uint;
1122                 unsafe {
1123                     self.str_buffer.set_len(new_size);
1124                 }
1125             }
1126             InternalIndex(_) => {}
1127         }
1128         self.stack.pop();
1129     }
1130
1131     // Used by Parser to test whether the top-most element is an index.
1132     fn last_is_index(&self) -> bool {
1133         if self.is_empty() { return false; }
1134         return match *self.stack.last().unwrap() {
1135             InternalIndex(_) => true,
1136             _ => false,
1137         }
1138     }
1139
1140     // Used by Parser to increment the index of the top-most element.
1141     fn bump_index(&mut self) {
1142         let len = self.stack.len();
1143         let idx = match *self.stack.last().unwrap() {
1144           InternalIndex(i) => { i + 1 }
1145           _ => { fail!(); }
1146         };
1147         *self.stack.get_mut(len - 1) = InternalIndex(idx);
1148     }
1149 }
1150
1151 /// A streaming JSON parser implemented as an iterator of JsonEvent, consuming
1152 /// an iterator of char.
1153 pub struct Parser<T> {
1154     rdr: T,
1155     ch: Option<char>,
1156     line: uint,
1157     col: uint,
1158     // We maintain a stack representing where we are in the logical structure
1159     // of the JSON stream.
1160     stack: Stack,
1161     // A state machine is kept to make it possible to interupt and resume parsing.
1162     state: ParserState,
1163 }
1164
1165 impl<T: Iterator<char>> Iterator<JsonEvent> for Parser<T> {
1166     fn next(&mut self) -> Option<JsonEvent> {
1167         if self.state == ParseFinished {
1168             return None;
1169         }
1170
1171         if self.state == ParseBeforeFinish {
1172             self.parse_whitespace();
1173             // Make sure there is no trailing characters.
1174             if self.eof() {
1175                 self.state = ParseFinished;
1176                 return None;
1177             } else {
1178                 return Some(self.error_event(TrailingCharacters));
1179             }
1180         }
1181
1182         return Some(self.parse());
1183     }
1184 }
1185
1186 impl<T: Iterator<char>> Parser<T> {
1187     /// Creates the JSON parser.
1188     pub fn new(rdr: T) -> Parser<T> {
1189         let mut p = Parser {
1190             rdr: rdr,
1191             ch: Some('\x00'),
1192             line: 1,
1193             col: 0,
1194             stack: Stack::new(),
1195             state: ParseStart,
1196         };
1197         p.bump();
1198         return p;
1199     }
1200
1201     /// Provides access to the current position in the logical structure of the
1202     /// JSON stream.
1203     pub fn stack<'l>(&'l self) -> &'l Stack {
1204         return &'l self.stack;
1205     }
1206
1207     fn eof(&self) -> bool { self.ch.is_none() }
1208     fn ch_or_null(&self) -> char { self.ch.unwrap_or('\x00') }
1209     fn bump(&mut self) {
1210         self.ch = self.rdr.next();
1211
1212         if self.ch_is('\n') {
1213             self.line += 1u;
1214             self.col = 1u;
1215         } else {
1216             self.col += 1u;
1217         }
1218     }
1219
1220     fn next_char(&mut self) -> Option<char> {
1221         self.bump();
1222         self.ch
1223     }
1224     fn ch_is(&self, c: char) -> bool {
1225         self.ch == Some(c)
1226     }
1227
1228     fn error<T>(&self, reason: ErrorCode) -> Result<T, ParserError> {
1229         Err(SyntaxError(reason, self.line, self.col))
1230     }
1231
1232     fn parse_whitespace(&mut self) {
1233         while self.ch_is(' ') ||
1234               self.ch_is('\n') ||
1235               self.ch_is('\t') ||
1236               self.ch_is('\r') { self.bump(); }
1237     }
1238
1239     fn parse_number(&mut self) -> Result<f64, ParserError> {
1240         let mut neg = 1.0;
1241
1242         if self.ch_is('-') {
1243             self.bump();
1244             neg = -1.0;
1245         }
1246
1247         let mut res = match self.parse_integer() {
1248           Ok(res) => res,
1249           Err(e) => return Err(e)
1250         };
1251
1252         if self.ch_is('.') {
1253             match self.parse_decimal(res) {
1254               Ok(r) => res = r,
1255               Err(e) => return Err(e)
1256             }
1257         }
1258
1259         if self.ch_is('e') || self.ch_is('E') {
1260             match self.parse_exponent(res) {
1261               Ok(r) => res = r,
1262               Err(e) => return Err(e)
1263             }
1264         }
1265
1266         Ok(neg * res)
1267     }
1268
1269     fn parse_integer(&mut self) -> Result<f64, ParserError> {
1270         let mut res = 0.0;
1271
1272         match self.ch_or_null() {
1273             '0' => {
1274                 self.bump();
1275
1276                 // There can be only one leading '0'.
1277                 match self.ch_or_null() {
1278                     '0' .. '9' => return self.error(InvalidNumber),
1279                     _ => ()
1280                 }
1281             },
1282             '1' .. '9' => {
1283                 while !self.eof() {
1284                     match self.ch_or_null() {
1285                         c @ '0' .. '9' => {
1286                             res *= 10.0;
1287                             res += ((c as int) - ('0' as int)) as f64;
1288                             self.bump();
1289                         }
1290                         _ => break,
1291                     }
1292                 }
1293             }
1294             _ => return self.error(InvalidNumber),
1295         }
1296         Ok(res)
1297     }
1298
1299     fn parse_decimal(&mut self, res: f64) -> Result<f64, ParserError> {
1300         self.bump();
1301
1302         // Make sure a digit follows the decimal place.
1303         match self.ch_or_null() {
1304             '0' .. '9' => (),
1305              _ => return self.error(InvalidNumber)
1306         }
1307
1308         let mut res = res;
1309         let mut dec = 1.0;
1310         while !self.eof() {
1311             match self.ch_or_null() {
1312                 c @ '0' .. '9' => {
1313                     dec /= 10.0;
1314                     res += (((c as int) - ('0' as int)) as f64) * dec;
1315                     self.bump();
1316                 }
1317                 _ => break,
1318             }
1319         }
1320
1321         Ok(res)
1322     }
1323
1324     fn parse_exponent(&mut self, mut res: f64) -> Result<f64, ParserError> {
1325         self.bump();
1326
1327         let mut exp = 0u;
1328         let mut neg_exp = false;
1329
1330         if self.ch_is('+') {
1331             self.bump();
1332         } else if self.ch_is('-') {
1333             self.bump();
1334             neg_exp = true;
1335         }
1336
1337         // Make sure a digit follows the exponent place.
1338         match self.ch_or_null() {
1339             '0' .. '9' => (),
1340             _ => return self.error(InvalidNumber)
1341         }
1342         while !self.eof() {
1343             match self.ch_or_null() {
1344                 c @ '0' .. '9' => {
1345                     exp *= 10;
1346                     exp += (c as uint) - ('0' as uint);
1347
1348                     self.bump();
1349                 }
1350                 _ => break
1351             }
1352         }
1353
1354         let exp: f64 = num::pow(10u as f64, exp);
1355         if neg_exp {
1356             res /= exp;
1357         } else {
1358             res *= exp;
1359         }
1360
1361         Ok(res)
1362     }
1363
1364     fn decode_hex_escape(&mut self) -> Result<u16, ParserError> {
1365         let mut i = 0u;
1366         let mut n = 0u16;
1367         while i < 4u && !self.eof() {
1368             self.bump();
1369             n = match self.ch_or_null() {
1370                 c @ '0' .. '9' => n * 16_u16 + ((c as u16) - ('0' as u16)),
1371                 'a' | 'A' => n * 16_u16 + 10_u16,
1372                 'b' | 'B' => n * 16_u16 + 11_u16,
1373                 'c' | 'C' => n * 16_u16 + 12_u16,
1374                 'd' | 'D' => n * 16_u16 + 13_u16,
1375                 'e' | 'E' => n * 16_u16 + 14_u16,
1376                 'f' | 'F' => n * 16_u16 + 15_u16,
1377                 _ => return self.error(InvalidEscape)
1378             };
1379
1380             i += 1u;
1381         }
1382
1383         // Error out if we didn't parse 4 digits.
1384         if i != 4u {
1385             return self.error(InvalidEscape);
1386         }
1387
1388         Ok(n)
1389     }
1390
1391     fn parse_str(&mut self) -> Result<String, ParserError> {
1392         let mut escape = false;
1393         let mut res = String::new();
1394
1395         loop {
1396             self.bump();
1397             if self.eof() {
1398                 return self.error(EOFWhileParsingString);
1399             }
1400
1401             if escape {
1402                 match self.ch_or_null() {
1403                     '"' => res.push_char('"'),
1404                     '\\' => res.push_char('\\'),
1405                     '/' => res.push_char('/'),
1406                     'b' => res.push_char('\x08'),
1407                     'f' => res.push_char('\x0c'),
1408                     'n' => res.push_char('\n'),
1409                     'r' => res.push_char('\r'),
1410                     't' => res.push_char('\t'),
1411                     'u' => match try!(self.decode_hex_escape()) {
1412                         0xDC00 .. 0xDFFF => return self.error(LoneLeadingSurrogateInHexEscape),
1413
1414                         // Non-BMP characters are encoded as a sequence of
1415                         // two hex escapes, representing UTF-16 surrogates.
1416                         n1 @ 0xD800 .. 0xDBFF => {
1417                             let c1 = self.next_char();
1418                             let c2 = self.next_char();
1419                             match (c1, c2) {
1420                                 (Some('\\'), Some('u')) => (),
1421                                 _ => return self.error(UnexpectedEndOfHexEscape),
1422                             }
1423
1424                             let buf = [n1, try!(self.decode_hex_escape())];
1425                             match str::utf16_items(buf.as_slice()).next() {
1426                                 Some(ScalarValue(c)) => res.push_char(c),
1427                                 _ => return self.error(LoneLeadingSurrogateInHexEscape),
1428                             }
1429                         }
1430
1431                         n => match char::from_u32(n as u32) {
1432                             Some(c) => res.push_char(c),
1433                             None => return self.error(InvalidUnicodeCodePoint),
1434                         },
1435                     },
1436                     _ => return self.error(InvalidEscape),
1437                 }
1438                 escape = false;
1439             } else if self.ch_is('\\') {
1440                 escape = true;
1441             } else {
1442                 match self.ch {
1443                     Some('"') => {
1444                         self.bump();
1445                         return Ok(res);
1446                     },
1447                     Some(c) => res.push_char(c),
1448                     None => unreachable!()
1449                 }
1450             }
1451         }
1452     }
1453
1454     // Invoked at each iteration, consumes the stream until it has enough
1455     // information to return a JsonEvent.
1456     // Manages an internal state so that parsing can be interrupted and resumed.
1457     // Also keeps track of the position in the logical structure of the json
1458     // stream int the form of a stack that can be queried by the user usng the
1459     // stack() method.
1460     fn parse(&mut self) -> JsonEvent {
1461         loop {
1462             // The only paths where the loop can spin a new iteration
1463             // are in the cases ParseListComma and ParseObjectComma if ','
1464             // is parsed. In these cases the state is set to (respectively)
1465             // ParseList(false) and ParseObject(false), which always return,
1466             // so there is no risk of getting stuck in an infinite loop.
1467             // All other paths return before the end of the loop's iteration.
1468             self.parse_whitespace();
1469
1470             match self.state {
1471                 ParseStart => {
1472                     return self.parse_start();
1473                 }
1474                 ParseList(first) => {
1475                     return self.parse_list(first);
1476                 }
1477                 ParseListComma => {
1478                     match self.parse_list_comma_or_end() {
1479                         Some(evt) => { return evt; }
1480                         None => {}
1481                     }
1482                 }
1483                 ParseObject(first) => {
1484                     return self.parse_object(first);
1485                 }
1486                 ParseObjectComma => {
1487                     self.stack.pop();
1488                     if self.ch_is(',') {
1489                         self.state = ParseObject(false);
1490                         self.bump();
1491                     } else {
1492                         return self.parse_object_end();
1493                     }
1494                 }
1495                 _ => {
1496                     return self.error_event(InvalidSyntax);
1497                 }
1498             }
1499         }
1500     }
1501
1502     fn parse_start(&mut self) -> JsonEvent {
1503         let val = self.parse_value();
1504         self.state = match val {
1505             Error(_) => { ParseFinished }
1506             ListStart => { ParseList(true) }
1507             ObjectStart => { ParseObject(true) }
1508             _ => { ParseBeforeFinish }
1509         };
1510         return val;
1511     }
1512
1513     fn parse_list(&mut self, first: bool) -> JsonEvent {
1514         if self.ch_is(']') {
1515             if !first {
1516                 return self.error_event(InvalidSyntax);
1517             }
1518             if self.stack.is_empty() {
1519                 self.state = ParseBeforeFinish;
1520             } else {
1521                 self.state = if self.stack.last_is_index() {
1522                     ParseListComma
1523                 } else {
1524                     ParseObjectComma
1525                 }
1526             }
1527             self.bump();
1528             return ListEnd;
1529         }
1530         if first {
1531             self.stack.push_index(0);
1532         }
1533
1534         let val = self.parse_value();
1535
1536         self.state = match val {
1537             Error(_) => { ParseFinished }
1538             ListStart => { ParseList(true) }
1539             ObjectStart => { ParseObject(true) }
1540             _ => { ParseListComma }
1541         };
1542         return val;
1543     }
1544
1545     fn parse_list_comma_or_end(&mut self) -> Option<JsonEvent> {
1546         if self.ch_is(',') {
1547             self.stack.bump_index();
1548             self.state = ParseList(false);
1549             self.bump();
1550             return None;
1551         } else if self.ch_is(']') {
1552             self.stack.pop();
1553             if self.stack.is_empty() {
1554                 self.state = ParseBeforeFinish;
1555             } else {
1556                 self.state = if self.stack.last_is_index() {
1557                     ParseListComma
1558                 } else {
1559                     ParseObjectComma
1560                 }
1561             }
1562             self.bump();
1563             return Some(ListEnd);
1564         } else if self.eof() {
1565             return Some(self.error_event(EOFWhileParsingList));
1566         } else {
1567             return Some(self.error_event(InvalidSyntax));
1568         }
1569     }
1570
1571     fn parse_object(&mut self, first: bool) -> JsonEvent {
1572         if self.ch_is('}') {
1573             if !first {
1574                 self.stack.pop();
1575             }
1576             if self.stack.is_empty() {
1577                 self.state = ParseBeforeFinish;
1578             } else {
1579                 self.state = if self.stack.last_is_index() {
1580                     ParseListComma
1581                 } else {
1582                     ParseObjectComma
1583                 }
1584             }
1585             self.bump();
1586             return ObjectEnd;
1587         }
1588         if self.eof() {
1589             return self.error_event(EOFWhileParsingObject);
1590         }
1591         if !self.ch_is('"') {
1592             return self.error_event(KeyMustBeAString);
1593         }
1594         let s = match self.parse_str() {
1595             Ok(s) => { s }
1596             Err(e) => {
1597                 self.state = ParseFinished;
1598                 return Error(e);
1599             }
1600         };
1601         self.parse_whitespace();
1602         if self.eof() {
1603             return self.error_event(EOFWhileParsingObject);
1604         } else if self.ch_or_null() != ':' {
1605             return self.error_event(ExpectedColon);
1606         }
1607         self.stack.push_key(s);
1608         self.bump();
1609         self.parse_whitespace();
1610
1611         let val = self.parse_value();
1612
1613         self.state = match val {
1614             Error(_) => { ParseFinished }
1615             ListStart => { ParseList(true) }
1616             ObjectStart => { ParseObject(true) }
1617             _ => { ParseObjectComma }
1618         };
1619         return val;
1620     }
1621
1622     fn parse_object_end(&mut self) -> JsonEvent {
1623         if self.ch_is('}') {
1624             if self.stack.is_empty() {
1625                 self.state = ParseBeforeFinish;
1626             } else {
1627                 self.state = if self.stack.last_is_index() {
1628                     ParseListComma
1629                 } else {
1630                     ParseObjectComma
1631                 }
1632             }
1633             self.bump();
1634             return ObjectEnd;
1635         } else if self.eof() {
1636             return self.error_event(EOFWhileParsingObject);
1637         } else {
1638             return self.error_event(InvalidSyntax);
1639         }
1640     }
1641
1642     fn parse_value(&mut self) -> JsonEvent {
1643         if self.eof() { return self.error_event(EOFWhileParsingValue); }
1644         match self.ch_or_null() {
1645             'n' => { return self.parse_ident("ull", NullValue); }
1646             't' => { return self.parse_ident("rue", BooleanValue(true)); }
1647             'f' => { return self.parse_ident("alse", BooleanValue(false)); }
1648             '0' .. '9' | '-' => return match self.parse_number() {
1649                 Ok(f) => NumberValue(f),
1650                 Err(e) => Error(e),
1651             },
1652             '"' => return match self.parse_str() {
1653                 Ok(s) => StringValue(s),
1654                 Err(e) => Error(e),
1655             },
1656             '[' => {
1657                 self.bump();
1658                 return ListStart;
1659             }
1660             '{' => {
1661                 self.bump();
1662                 return ObjectStart;
1663             }
1664             _ => { return self.error_event(InvalidSyntax); }
1665         }
1666     }
1667
1668     fn parse_ident(&mut self, ident: &str, value: JsonEvent) -> JsonEvent {
1669         if ident.chars().all(|c| Some(c) == self.next_char()) {
1670             self.bump();
1671             value
1672         } else {
1673             Error(SyntaxError(InvalidSyntax, self.line, self.col))
1674         }
1675     }
1676
1677     fn error_event(&mut self, reason: ErrorCode) -> JsonEvent {
1678         self.state = ParseFinished;
1679         Error(SyntaxError(reason, self.line, self.col))
1680     }
1681 }
1682
1683 /// A Builder consumes a json::Parser to create a generic Json structure.
1684 pub struct Builder<T> {
1685     parser: Parser<T>,
1686     token: Option<JsonEvent>,
1687 }
1688
1689 impl<T: Iterator<char>> Builder<T> {
1690     /// Create a JSON Builder.
1691     pub fn new(src: T) -> Builder<T> {
1692         Builder {
1693             parser: Parser::new(src),
1694             token: None,
1695         }
1696     }
1697
1698     // Decode a Json value from a Parser.
1699     pub fn build(&mut self) -> Result<Json, BuilderError> {
1700         self.bump();
1701         let result = self.build_value();
1702         self.bump();
1703         match self.token {
1704             None => {}
1705             Some(Error(e)) => { return Err(e); }
1706             ref tok => { fail!("unexpected token {}", tok.clone()); }
1707         }
1708         return result;
1709     }
1710
1711     fn bump(&mut self) {
1712         self.token = self.parser.next();
1713     }
1714
1715     fn build_value(&mut self) -> Result<Json, BuilderError> {
1716         return match self.token {
1717             Some(NullValue) => { Ok(Null) }
1718             Some(NumberValue(n)) => { Ok(Number(n)) }
1719             Some(BooleanValue(b)) => { Ok(Boolean(b)) }
1720             Some(StringValue(ref mut s)) => {
1721                 let mut temp = String::new();
1722                 swap(s, &mut temp);
1723                 Ok(String(temp))
1724             }
1725             Some(Error(e)) => { Err(e) }
1726             Some(ListStart) => { self.build_list() }
1727             Some(ObjectStart) => { self.build_object() }
1728             Some(ObjectEnd) => { self.parser.error(InvalidSyntax) }
1729             Some(ListEnd) => { self.parser.error(InvalidSyntax) }
1730             None => { self.parser.error(EOFWhileParsingValue) }
1731         }
1732     }
1733
1734     fn build_list(&mut self) -> Result<Json, BuilderError> {
1735         self.bump();
1736         let mut values = Vec::new();
1737
1738         loop {
1739             if self.token == Some(ListEnd) {
1740                 return Ok(List(values.move_iter().collect()));
1741             }
1742             match self.build_value() {
1743                 Ok(v) => values.push(v),
1744                 Err(e) => { return Err(e) }
1745             }
1746             self.bump();
1747         }
1748     }
1749
1750     fn build_object(&mut self) -> Result<Json, BuilderError> {
1751         self.bump();
1752
1753         let mut values = box TreeMap::new();
1754
1755         while self.token != None {
1756             match self.token {
1757                 Some(ObjectEnd) => { return Ok(Object(values)); }
1758                 Some(Error(e)) => { return Err(e); }
1759                 None => { break; }
1760                 _ => {}
1761             }
1762             let key = match self.parser.stack().top() {
1763                 Some(Key(k)) => { k.to_string() }
1764                 _ => { fail!("invalid state"); }
1765             };
1766             match self.build_value() {
1767                 Ok(value) => { values.insert(key, value); }
1768                 Err(e) => { return Err(e); }
1769             }
1770             self.bump();
1771         }
1772         return self.parser.error(EOFWhileParsingObject);
1773     }
1774 }
1775
1776
1777 /// Decodes a json value from an `&mut io::Reader`
1778 pub fn from_reader(rdr: &mut io::Reader) -> Result<Json, BuilderError> {
1779     let contents = match rdr.read_to_end() {
1780         Ok(c) => c,
1781         Err(e) => return Err(io_error_to_error(e))
1782     };
1783     let s = match str::from_utf8(contents.as_slice()) {
1784         Some(s) => s.to_string(),
1785         None => return Err(SyntaxError(NotUtf8, 0, 0))
1786     };
1787     let mut builder = Builder::new(s.as_slice().chars());
1788     builder.build()
1789 }
1790
1791 /// Decodes a json value from a string
1792 pub fn from_str(s: &str) -> Result<Json, BuilderError> {
1793     let mut builder = Builder::new(s.chars());
1794     return builder.build();
1795 }
1796
1797 /// A structure to decode JSON to values in rust.
1798 pub struct Decoder {
1799     stack: Vec<Json>,
1800 }
1801
1802 impl Decoder {
1803     /// Creates a new decoder instance for decoding the specified JSON value.
1804     pub fn new(json: Json) -> Decoder {
1805         Decoder {
1806             stack: vec!(json),
1807         }
1808     }
1809 }
1810
1811 impl Decoder {
1812     fn pop(&mut self) -> Json {
1813         self.stack.pop().unwrap()
1814     }
1815 }
1816
1817 macro_rules! expect(
1818     ($e:expr, Null) => ({
1819         match $e {
1820             Null => Ok(()),
1821             other => Err(ExpectedError("Null".to_string(),
1822                                        format!("{}", other)))
1823         }
1824     });
1825     ($e:expr, $t:ident) => ({
1826         match $e {
1827             $t(v) => Ok(v),
1828             other => {
1829                 Err(ExpectedError(stringify!($t).to_string(),
1830                                   format!("{}", other)))
1831             }
1832         }
1833     })
1834 )
1835
1836 impl ::Decoder<DecoderError> for Decoder {
1837     fn read_nil(&mut self) -> DecodeResult<()> {
1838         debug!("read_nil");
1839         try!(expect!(self.pop(), Null));
1840         Ok(())
1841     }
1842
1843     fn read_u64(&mut self)  -> DecodeResult<u64 > { Ok(try!(self.read_f64()) as u64) }
1844     fn read_u32(&mut self)  -> DecodeResult<u32 > { Ok(try!(self.read_f64()) as u32) }
1845     fn read_u16(&mut self)  -> DecodeResult<u16 > { Ok(try!(self.read_f64()) as u16) }
1846     fn read_u8 (&mut self)  -> DecodeResult<u8  > { Ok(try!(self.read_f64()) as u8) }
1847     fn read_uint(&mut self) -> DecodeResult<uint> { Ok(try!(self.read_f64()) as uint) }
1848
1849     fn read_i64(&mut self) -> DecodeResult<i64> { Ok(try!(self.read_f64()) as i64) }
1850     fn read_i32(&mut self) -> DecodeResult<i32> { Ok(try!(self.read_f64()) as i32) }
1851     fn read_i16(&mut self) -> DecodeResult<i16> { Ok(try!(self.read_f64()) as i16) }
1852     fn read_i8 (&mut self) -> DecodeResult<i8 > { Ok(try!(self.read_f64()) as i8) }
1853     fn read_int(&mut self) -> DecodeResult<int> { Ok(try!(self.read_f64()) as int) }
1854
1855     fn read_bool(&mut self) -> DecodeResult<bool> {
1856         debug!("read_bool");
1857         Ok(try!(expect!(self.pop(), Boolean)))
1858     }
1859
1860     fn read_f64(&mut self) -> DecodeResult<f64> {
1861         use std::from_str::FromStr;
1862         debug!("read_f64");
1863         match self.pop() {
1864             Number(f) => Ok(f),
1865             String(s) => {
1866                 // re: #12967.. a type w/ numeric keys (ie HashMap<uint, V> etc)
1867                 // is going to have a string here, as per JSON spec..
1868                 Ok(FromStr::from_str(s.as_slice()).unwrap())
1869             },
1870             value => {
1871                 Err(ExpectedError("Number".to_string(),
1872                                   format!("{}", value)))
1873             }
1874         }
1875     }
1876
1877     fn read_f32(&mut self) -> DecodeResult<f32> { Ok(try!(self.read_f64()) as f32) }
1878
1879     fn read_char(&mut self) -> DecodeResult<char> {
1880         let s = try!(self.read_str());
1881         {
1882             let mut it = s.as_slice().chars();
1883             match (it.next(), it.next()) {
1884                 // exactly one character
1885                 (Some(c), None) => return Ok(c),
1886                 _ => ()
1887             }
1888         }
1889         Err(ExpectedError("single character string".to_string(),
1890                           format!("{}", s)))
1891     }
1892
1893     fn read_str(&mut self) -> DecodeResult<String> {
1894         debug!("read_str");
1895         Ok(try!(expect!(self.pop(), String)))
1896     }
1897
1898     fn read_enum<T>(&mut self,
1899                     name: &str,
1900                     f: |&mut Decoder| -> DecodeResult<T>) -> DecodeResult<T> {
1901         debug!("read_enum({})", name);
1902         f(self)
1903     }
1904
1905     fn read_enum_variant<T>(&mut self,
1906                             names: &[&str],
1907                             f: |&mut Decoder, uint| -> DecodeResult<T>)
1908                             -> DecodeResult<T> {
1909         debug!("read_enum_variant(names={})", names);
1910         let name = match self.pop() {
1911             String(s) => s,
1912             Object(mut o) => {
1913                 let n = match o.pop(&"variant".to_string()) {
1914                     Some(String(s)) => s,
1915                     Some(val) => {
1916                         return Err(ExpectedError("String".to_string(),
1917                                                  format!("{}", val)))
1918                     }
1919                     None => {
1920                         return Err(MissingFieldError("variant".to_string()))
1921                     }
1922                 };
1923                 match o.pop(&"fields".to_string()) {
1924                     Some(List(l)) => {
1925                         for field in l.move_iter().rev() {
1926                             self.stack.push(field.clone());
1927                         }
1928                     },
1929                     Some(val) => {
1930                         return Err(ExpectedError("List".to_string(),
1931                                                  format!("{}", val)))
1932                     }
1933                     None => {
1934                         return Err(MissingFieldError("fields".to_string()))
1935                     }
1936                 }
1937                 n
1938             }
1939             json => {
1940                 return Err(ExpectedError("String or Object".to_string(),
1941                                          format!("{}", json)))
1942             }
1943         };
1944         let idx = match names.iter()
1945                              .position(|n| {
1946                                  str::eq_slice(*n, name.as_slice())
1947                              }) {
1948             Some(idx) => idx,
1949             None => return Err(UnknownVariantError(name))
1950         };
1951         f(self, idx)
1952     }
1953
1954     fn read_enum_variant_arg<T>(&mut self, idx: uint, f: |&mut Decoder| -> DecodeResult<T>)
1955                                 -> DecodeResult<T> {
1956         debug!("read_enum_variant_arg(idx={})", idx);
1957         f(self)
1958     }
1959
1960     fn read_enum_struct_variant<T>(&mut self,
1961                                    names: &[&str],
1962                                    f: |&mut Decoder, uint| -> DecodeResult<T>)
1963                                    -> DecodeResult<T> {
1964         debug!("read_enum_struct_variant(names={})", names);
1965         self.read_enum_variant(names, f)
1966     }
1967
1968
1969     fn read_enum_struct_variant_field<T>(&mut self,
1970                                          name: &str,
1971                                          idx: uint,
1972                                          f: |&mut Decoder| -> DecodeResult<T>)
1973                                          -> DecodeResult<T> {
1974         debug!("read_enum_struct_variant_field(name={}, idx={})", name, idx);
1975         self.read_enum_variant_arg(idx, f)
1976     }
1977
1978     fn read_struct<T>(&mut self,
1979                       name: &str,
1980                       len: uint,
1981                       f: |&mut Decoder| -> DecodeResult<T>)
1982                       -> DecodeResult<T> {
1983         debug!("read_struct(name={}, len={})", name, len);
1984         let value = try!(f(self));
1985         self.pop();
1986         Ok(value)
1987     }
1988
1989     fn read_struct_field<T>(&mut self,
1990                             name: &str,
1991                             idx: uint,
1992                             f: |&mut Decoder| -> DecodeResult<T>)
1993                             -> DecodeResult<T> {
1994         debug!("read_struct_field(name={}, idx={})", name, idx);
1995         let mut obj = try!(expect!(self.pop(), Object));
1996
1997         let value = match obj.pop(&name.to_string()) {
1998             None => return Err(MissingFieldError(name.to_string())),
1999             Some(json) => {
2000                 self.stack.push(json);
2001                 try!(f(self))
2002             }
2003         };
2004         self.stack.push(Object(obj));
2005         Ok(value)
2006     }
2007
2008     fn read_tuple<T>(&mut self, f: |&mut Decoder, uint| -> DecodeResult<T>) -> DecodeResult<T> {
2009         debug!("read_tuple()");
2010         self.read_seq(f)
2011     }
2012
2013     fn read_tuple_arg<T>(&mut self,
2014                          idx: uint,
2015                          f: |&mut Decoder| -> DecodeResult<T>) -> DecodeResult<T> {
2016         debug!("read_tuple_arg(idx={})", idx);
2017         self.read_seq_elt(idx, f)
2018     }
2019
2020     fn read_tuple_struct<T>(&mut self,
2021                             name: &str,
2022                             f: |&mut Decoder, uint| -> DecodeResult<T>)
2023                             -> DecodeResult<T> {
2024         debug!("read_tuple_struct(name={})", name);
2025         self.read_tuple(f)
2026     }
2027
2028     fn read_tuple_struct_arg<T>(&mut self,
2029                                 idx: uint,
2030                                 f: |&mut Decoder| -> DecodeResult<T>)
2031                                 -> DecodeResult<T> {
2032         debug!("read_tuple_struct_arg(idx={})", idx);
2033         self.read_tuple_arg(idx, f)
2034     }
2035
2036     fn read_option<T>(&mut self, f: |&mut Decoder, bool| -> DecodeResult<T>) -> DecodeResult<T> {
2037         match self.pop() {
2038             Null => f(self, false),
2039             value => { self.stack.push(value); f(self, true) }
2040         }
2041     }
2042
2043     fn read_seq<T>(&mut self, f: |&mut Decoder, uint| -> DecodeResult<T>) -> DecodeResult<T> {
2044         debug!("read_seq()");
2045         let list = try!(expect!(self.pop(), List));
2046         let len = list.len();
2047         for v in list.move_iter().rev() {
2048             self.stack.push(v);
2049         }
2050         f(self, len)
2051     }
2052
2053     fn read_seq_elt<T>(&mut self,
2054                        idx: uint,
2055                        f: |&mut Decoder| -> DecodeResult<T>) -> DecodeResult<T> {
2056         debug!("read_seq_elt(idx={})", idx);
2057         f(self)
2058     }
2059
2060     fn read_map<T>(&mut self, f: |&mut Decoder, uint| -> DecodeResult<T>) -> DecodeResult<T> {
2061         debug!("read_map()");
2062         let obj = try!(expect!(self.pop(), Object));
2063         let len = obj.len();
2064         for (key, value) in obj.move_iter() {
2065             self.stack.push(value);
2066             self.stack.push(String(key));
2067         }
2068         f(self, len)
2069     }
2070
2071     fn read_map_elt_key<T>(&mut self, idx: uint, f: |&mut Decoder| -> DecodeResult<T>)
2072                            -> DecodeResult<T> {
2073         debug!("read_map_elt_key(idx={})", idx);
2074         f(self)
2075     }
2076
2077     fn read_map_elt_val<T>(&mut self, idx: uint, f: |&mut Decoder| -> DecodeResult<T>)
2078                            -> DecodeResult<T> {
2079         debug!("read_map_elt_val(idx={})", idx);
2080         f(self)
2081     }
2082 }
2083
2084 /// Test if two json values are less than one another
2085 impl Ord for Json {
2086     fn lt(&self, other: &Json) -> bool {
2087         match *self {
2088             Number(f0) => {
2089                 match *other {
2090                     Number(f1) => f0 < f1,
2091                     String(_) | Boolean(_) | List(_) | Object(_) |
2092                     Null => true
2093                 }
2094             }
2095
2096             String(ref s0) => {
2097                 match *other {
2098                     Number(_) => false,
2099                     String(ref s1) => s0 < s1,
2100                     Boolean(_) | List(_) | Object(_) | Null => true
2101                 }
2102             }
2103
2104             Boolean(b0) => {
2105                 match *other {
2106                     Number(_) | String(_) => false,
2107                     Boolean(b1) => b0 < b1,
2108                     List(_) | Object(_) | Null => true
2109                 }
2110             }
2111
2112             List(ref l0) => {
2113                 match *other {
2114                     Number(_) | String(_) | Boolean(_) => false,
2115                     List(ref l1) => (*l0) < (*l1),
2116                     Object(_) | Null => true
2117                 }
2118             }
2119
2120             Object(ref d0) => {
2121                 match *other {
2122                     Number(_) | String(_) | Boolean(_) | List(_) => false,
2123                     Object(ref d1) => d0 < d1,
2124                     Null => true
2125                 }
2126             }
2127
2128             Null => {
2129                 match *other {
2130                     Number(_) | String(_) | Boolean(_) | List(_) |
2131                     Object(_) =>
2132                         false,
2133                     Null => true
2134                 }
2135             }
2136         }
2137     }
2138 }
2139
2140 /// A trait for converting values to JSON
2141 pub trait ToJson {
2142     /// Converts the value of `self` to an instance of JSON
2143     fn to_json(&self) -> Json;
2144 }
2145
2146 impl ToJson for Json {
2147     fn to_json(&self) -> Json { (*self).clone() }
2148 }
2149
2150 impl ToJson for int {
2151     fn to_json(&self) -> Json { Number(*self as f64) }
2152 }
2153
2154 impl ToJson for i8 {
2155     fn to_json(&self) -> Json { Number(*self as f64) }
2156 }
2157
2158 impl ToJson for i16 {
2159     fn to_json(&self) -> Json { Number(*self as f64) }
2160 }
2161
2162 impl ToJson for i32 {
2163     fn to_json(&self) -> Json { Number(*self as f64) }
2164 }
2165
2166 impl ToJson for i64 {
2167     fn to_json(&self) -> Json { Number(*self as f64) }
2168 }
2169
2170 impl ToJson for uint {
2171     fn to_json(&self) -> Json { Number(*self as f64) }
2172 }
2173
2174 impl ToJson for u8 {
2175     fn to_json(&self) -> Json { Number(*self as f64) }
2176 }
2177
2178 impl ToJson for u16 {
2179     fn to_json(&self) -> Json { Number(*self as f64) }
2180 }
2181
2182 impl ToJson for u32 {
2183     fn to_json(&self) -> Json { Number(*self as f64) }
2184 }
2185
2186 impl ToJson for u64 {
2187     fn to_json(&self) -> Json { Number(*self as f64) }
2188 }
2189
2190 impl ToJson for f32 {
2191     fn to_json(&self) -> Json { Number(*self as f64) }
2192 }
2193
2194 impl ToJson for f64 {
2195     fn to_json(&self) -> Json { Number(*self) }
2196 }
2197
2198 impl ToJson for () {
2199     fn to_json(&self) -> Json { Null }
2200 }
2201
2202 impl ToJson for bool {
2203     fn to_json(&self) -> Json { Boolean(*self) }
2204 }
2205
2206 impl ToJson for String {
2207     fn to_json(&self) -> Json { String((*self).clone()) }
2208 }
2209
2210 impl<A:ToJson,B:ToJson> ToJson for (A, B) {
2211     fn to_json(&self) -> Json {
2212         match *self {
2213           (ref a, ref b) => {
2214             List(vec![a.to_json(), b.to_json()])
2215           }
2216         }
2217     }
2218 }
2219
2220 impl<A:ToJson,B:ToJson,C:ToJson> ToJson for (A, B, C) {
2221     fn to_json(&self) -> Json {
2222         match *self {
2223           (ref a, ref b, ref c) => {
2224             List(vec![a.to_json(), b.to_json(), c.to_json()])
2225           }
2226         }
2227     }
2228 }
2229
2230 impl<A:ToJson> ToJson for ~[A] {
2231     fn to_json(&self) -> Json { List(self.iter().map(|elt| elt.to_json()).collect()) }
2232 }
2233
2234 impl<A:ToJson> ToJson for Vec<A> {
2235     fn to_json(&self) -> Json { List(self.iter().map(|elt| elt.to_json()).collect()) }
2236 }
2237
2238 impl<A:ToJson> ToJson for TreeMap<String, A> {
2239     fn to_json(&self) -> Json {
2240         let mut d = TreeMap::new();
2241         for (key, value) in self.iter() {
2242             d.insert((*key).clone(), value.to_json());
2243         }
2244         Object(box d)
2245     }
2246 }
2247
2248 impl<A:ToJson> ToJson for HashMap<String, A> {
2249     fn to_json(&self) -> Json {
2250         let mut d = TreeMap::new();
2251         for (key, value) in self.iter() {
2252             d.insert((*key).clone(), value.to_json());
2253         }
2254         Object(box d)
2255     }
2256 }
2257
2258 impl<A:ToJson> ToJson for Option<A> {
2259     fn to_json(&self) -> Json {
2260         match *self {
2261           None => Null,
2262           Some(ref value) => value.to_json()
2263         }
2264     }
2265 }
2266
2267 impl fmt::Show for Json {
2268     /// Encodes a json value into a string
2269     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2270         self.to_writer(f).map_err(|_| fmt::WriteError)
2271     }
2272 }
2273
2274 #[cfg(test)]
2275 mod tests {
2276     extern crate test;
2277     use self::test::Bencher;
2278     use {Encodable, Decodable};
2279     use super::{Encoder, Decoder, Error, Boolean, Number, List, String, Null,
2280                 PrettyEncoder, Object, Json, from_str, ParseError, ExpectedError,
2281                 MissingFieldError, UnknownVariantError, DecodeResult, DecoderError,
2282                 JsonEvent, Parser, StackElement,
2283                 ObjectStart, ObjectEnd, ListStart, ListEnd, BooleanValue, NumberValue, StringValue,
2284                 NullValue, SyntaxError, Key, Index, Stack,
2285                 InvalidSyntax, InvalidNumber, EOFWhileParsingObject, EOFWhileParsingList,
2286                 EOFWhileParsingValue, EOFWhileParsingString, KeyMustBeAString, ExpectedColon,
2287                 TrailingCharacters};
2288     use std::io;
2289     use collections::TreeMap;
2290
2291     #[deriving(Eq, Encodable, Decodable, Show)]
2292     enum Animal {
2293         Dog,
2294         Frog(String, int)
2295     }
2296
2297     #[deriving(Eq, Encodable, Decodable, Show)]
2298     struct Inner {
2299         a: (),
2300         b: uint,
2301         c: Vec<String>,
2302     }
2303
2304     #[deriving(Eq, Encodable, Decodable, Show)]
2305     struct Outer {
2306         inner: Vec<Inner>,
2307     }
2308
2309     fn mk_object(items: &[(String, Json)]) -> Json {
2310         let mut d = box TreeMap::new();
2311
2312         for item in items.iter() {
2313             match *item {
2314                 (ref key, ref value) => { d.insert((*key).clone(), (*value).clone()); },
2315             }
2316         };
2317
2318         Object(d)
2319     }
2320
2321     #[test]
2322     fn test_write_null() {
2323         assert_eq!(Null.to_str().into_string(), "null".to_string());
2324         assert_eq!(Null.to_pretty_str().into_string(), "null".to_string());
2325     }
2326
2327
2328     #[test]
2329     fn test_write_number() {
2330         assert_eq!(Number(3.0).to_str().into_string(), "3".to_string());
2331         assert_eq!(Number(3.0).to_pretty_str().into_string(), "3".to_string());
2332
2333         assert_eq!(Number(3.1).to_str().into_string(), "3.1".to_string());
2334         assert_eq!(Number(3.1).to_pretty_str().into_string(), "3.1".to_string());
2335
2336         assert_eq!(Number(-1.5).to_str().into_string(), "-1.5".to_string());
2337         assert_eq!(Number(-1.5).to_pretty_str().into_string(), "-1.5".to_string());
2338
2339         assert_eq!(Number(0.5).to_str().into_string(), "0.5".to_string());
2340         assert_eq!(Number(0.5).to_pretty_str().into_string(), "0.5".to_string());
2341     }
2342
2343     #[test]
2344     fn test_write_str() {
2345         assert_eq!(String("".to_string()).to_str().into_string(), "\"\"".to_string());
2346         assert_eq!(String("".to_string()).to_pretty_str().into_string(), "\"\"".to_string());
2347
2348         assert_eq!(String("foo".to_string()).to_str().into_string(), "\"foo\"".to_string());
2349         assert_eq!(String("foo".to_string()).to_pretty_str().into_string(), "\"foo\"".to_string());
2350     }
2351
2352     #[test]
2353     fn test_write_bool() {
2354         assert_eq!(Boolean(true).to_str().into_string(), "true".to_string());
2355         assert_eq!(Boolean(true).to_pretty_str().into_string(), "true".to_string());
2356
2357         assert_eq!(Boolean(false).to_str().into_string(), "false".to_string());
2358         assert_eq!(Boolean(false).to_pretty_str().into_string(), "false".to_string());
2359     }
2360
2361     #[test]
2362     fn test_write_list() {
2363         assert_eq!(List(vec![]).to_str().into_string(), "[]".to_string());
2364         assert_eq!(List(vec![]).to_pretty_str().into_string(), "[]".to_string());
2365
2366         assert_eq!(List(vec![Boolean(true)]).to_str().into_string(), "[true]".to_string());
2367         assert_eq!(
2368             List(vec![Boolean(true)]).to_pretty_str().into_string(),
2369             "\
2370             [\n  \
2371                 true\n\
2372             ]".to_string()
2373         );
2374
2375         let long_test_list = List(vec![
2376             Boolean(false),
2377             Null,
2378             List(vec![String("foo\nbar".to_string()), Number(3.5)])]);
2379
2380         assert_eq!(long_test_list.to_str().into_string(),
2381             "[false,null,[\"foo\\nbar\",3.5]]".to_string());
2382         assert_eq!(
2383             long_test_list.to_pretty_str().into_string(),
2384             "\
2385             [\n  \
2386                 false,\n  \
2387                 null,\n  \
2388                 [\n    \
2389                     \"foo\\nbar\",\n    \
2390                     3.5\n  \
2391                 ]\n\
2392             ]".to_string()
2393         );
2394     }
2395
2396     #[test]
2397     fn test_write_object() {
2398         assert_eq!(mk_object([]).to_str().into_string(), "{}".to_string());
2399         assert_eq!(mk_object([]).to_pretty_str().into_string(), "{}".to_string());
2400
2401         assert_eq!(
2402             mk_object([
2403                 ("a".to_string(), Boolean(true))
2404             ]).to_str().into_string(),
2405             "{\"a\":true}".to_string()
2406         );
2407         assert_eq!(
2408             mk_object([("a".to_string(), Boolean(true))]).to_pretty_str(),
2409             "\
2410             {\n  \
2411                 \"a\": true\n\
2412             }".to_string()
2413         );
2414
2415         let complex_obj = mk_object([
2416                 ("b".to_string(), List(vec![
2417                     mk_object([("c".to_string(), String("\x0c\r".to_string()))]),
2418                     mk_object([("d".to_string(), String("".to_string()))])
2419                 ]))
2420             ]);
2421
2422         assert_eq!(
2423             complex_obj.to_str().into_string(),
2424             "{\
2425                 \"b\":[\
2426                     {\"c\":\"\\f\\r\"},\
2427                     {\"d\":\"\"}\
2428                 ]\
2429             }".to_string()
2430         );
2431         assert_eq!(
2432             complex_obj.to_pretty_str().into_string(),
2433             "\
2434             {\n  \
2435                 \"b\": [\n    \
2436                     {\n      \
2437                         \"c\": \"\\f\\r\"\n    \
2438                     },\n    \
2439                     {\n      \
2440                         \"d\": \"\"\n    \
2441                     }\n  \
2442                 ]\n\
2443             }".to_string()
2444         );
2445
2446         let a = mk_object([
2447             ("a".to_string(), Boolean(true)),
2448             ("b".to_string(), List(vec![
2449                 mk_object([("c".to_string(), String("\x0c\r".to_string()))]),
2450                 mk_object([("d".to_string(), String("".to_string()))])
2451             ]))
2452         ]);
2453
2454         // We can't compare the strings directly because the object fields be
2455         // printed in a different order.
2456         assert_eq!(a.clone(), from_str(a.to_str().as_slice()).unwrap());
2457         assert_eq!(a.clone(),
2458                    from_str(a.to_pretty_str().as_slice()).unwrap());
2459     }
2460
2461     fn with_str_writer(f: |&mut io::Writer|) -> String {
2462         use std::io::MemWriter;
2463         use std::str;
2464
2465         let mut m = MemWriter::new();
2466         f(&mut m as &mut io::Writer);
2467         str::from_utf8(m.unwrap().as_slice()).unwrap().to_string()
2468     }
2469
2470     #[test]
2471     fn test_write_enum() {
2472         let animal = Dog;
2473         assert_eq!(
2474             with_str_writer(|wr| {
2475                 let mut encoder = Encoder::new(wr);
2476                 animal.encode(&mut encoder).unwrap();
2477             }),
2478             "\"Dog\"".to_string()
2479         );
2480         assert_eq!(
2481             with_str_writer(|wr| {
2482                 let mut encoder = PrettyEncoder::new(wr);
2483                 animal.encode(&mut encoder).unwrap();
2484             }),
2485             "\"Dog\"".to_string()
2486         );
2487
2488         let animal = Frog("Henry".to_string(), 349);
2489         assert_eq!(
2490             with_str_writer(|wr| {
2491                 let mut encoder = Encoder::new(wr);
2492                 animal.encode(&mut encoder).unwrap();
2493             }),
2494             "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}".to_string()
2495         );
2496         assert_eq!(
2497             with_str_writer(|wr| {
2498                 let mut encoder = PrettyEncoder::new(wr);
2499                 animal.encode(&mut encoder).unwrap();
2500             }),
2501             "\
2502             [\n  \
2503                 \"Frog\",\n  \
2504                 \"Henry\",\n  \
2505                 349\n\
2506             ]".to_string()
2507         );
2508     }
2509
2510     #[test]
2511     fn test_write_some() {
2512         let value = Some("jodhpurs".to_string());
2513         let s = with_str_writer(|wr| {
2514             let mut encoder = Encoder::new(wr);
2515             value.encode(&mut encoder).unwrap();
2516         });
2517         assert_eq!(s, "\"jodhpurs\"".to_string());
2518
2519         let value = Some("jodhpurs".to_string());
2520         let s = with_str_writer(|wr| {
2521             let mut encoder = PrettyEncoder::new(wr);
2522             value.encode(&mut encoder).unwrap();
2523         });
2524         assert_eq!(s, "\"jodhpurs\"".to_string());
2525     }
2526
2527     #[test]
2528     fn test_write_none() {
2529         let value: Option<String> = None;
2530         let s = with_str_writer(|wr| {
2531             let mut encoder = Encoder::new(wr);
2532             value.encode(&mut encoder).unwrap();
2533         });
2534         assert_eq!(s, "null".to_string());
2535
2536         let s = with_str_writer(|wr| {
2537             let mut encoder = Encoder::new(wr);
2538             value.encode(&mut encoder).unwrap();
2539         });
2540         assert_eq!(s, "null".to_string());
2541     }
2542
2543     #[test]
2544     fn test_trailing_characters() {
2545         assert_eq!(from_str("nulla"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2546         assert_eq!(from_str("truea"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2547         assert_eq!(from_str("falsea"), Err(SyntaxError(TrailingCharacters, 1, 6)));
2548         assert_eq!(from_str("1a"),     Err(SyntaxError(TrailingCharacters, 1, 2)));
2549         assert_eq!(from_str("[]a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2550         assert_eq!(from_str("{}a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2551     }
2552
2553     #[test]
2554     fn test_read_identifiers() {
2555         assert_eq!(from_str("n"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2556         assert_eq!(from_str("nul"),  Err(SyntaxError(InvalidSyntax, 1, 4)));
2557         assert_eq!(from_str("t"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2558         assert_eq!(from_str("truz"), Err(SyntaxError(InvalidSyntax, 1, 4)));
2559         assert_eq!(from_str("f"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2560         assert_eq!(from_str("faz"),  Err(SyntaxError(InvalidSyntax, 1, 3)));
2561
2562         assert_eq!(from_str("null"), Ok(Null));
2563         assert_eq!(from_str("true"), Ok(Boolean(true)));
2564         assert_eq!(from_str("false"), Ok(Boolean(false)));
2565         assert_eq!(from_str(" null "), Ok(Null));
2566         assert_eq!(from_str(" true "), Ok(Boolean(true)));
2567         assert_eq!(from_str(" false "), Ok(Boolean(false)));
2568     }
2569
2570     #[test]
2571     fn test_decode_identifiers() {
2572         let mut decoder = Decoder::new(from_str("null").unwrap());
2573         let v: () = Decodable::decode(&mut decoder).unwrap();
2574         assert_eq!(v, ());
2575
2576         let mut decoder = Decoder::new(from_str("true").unwrap());
2577         let v: bool = Decodable::decode(&mut decoder).unwrap();
2578         assert_eq!(v, true);
2579
2580         let mut decoder = Decoder::new(from_str("false").unwrap());
2581         let v: bool = Decodable::decode(&mut decoder).unwrap();
2582         assert_eq!(v, false);
2583     }
2584
2585     #[test]
2586     fn test_read_number() {
2587         assert_eq!(from_str("+"),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2588         assert_eq!(from_str("."),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2589         assert_eq!(from_str("-"),   Err(SyntaxError(InvalidNumber, 1, 2)));
2590         assert_eq!(from_str("00"),  Err(SyntaxError(InvalidNumber, 1, 2)));
2591         assert_eq!(from_str("1."),  Err(SyntaxError(InvalidNumber, 1, 3)));
2592         assert_eq!(from_str("1e"),  Err(SyntaxError(InvalidNumber, 1, 3)));
2593         assert_eq!(from_str("1e+"), Err(SyntaxError(InvalidNumber, 1, 4)));
2594
2595         assert_eq!(from_str("3"), Ok(Number(3.0)));
2596         assert_eq!(from_str("3.1"), Ok(Number(3.1)));
2597         assert_eq!(from_str("-1.2"), Ok(Number(-1.2)));
2598         assert_eq!(from_str("0.4"), Ok(Number(0.4)));
2599         assert_eq!(from_str("0.4e5"), Ok(Number(0.4e5)));
2600         assert_eq!(from_str("0.4e+15"), Ok(Number(0.4e15)));
2601         assert_eq!(from_str("0.4e-01"), Ok(Number(0.4e-01)));
2602         assert_eq!(from_str(" 3 "), Ok(Number(3.0)));
2603     }
2604
2605     #[test]
2606     fn test_decode_numbers() {
2607         let mut decoder = Decoder::new(from_str("3").unwrap());
2608         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2609         assert_eq!(v, 3.0);
2610
2611         let mut decoder = Decoder::new(from_str("3.1").unwrap());
2612         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2613         assert_eq!(v, 3.1);
2614
2615         let mut decoder = Decoder::new(from_str("-1.2").unwrap());
2616         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2617         assert_eq!(v, -1.2);
2618
2619         let mut decoder = Decoder::new(from_str("0.4").unwrap());
2620         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2621         assert_eq!(v, 0.4);
2622
2623         let mut decoder = Decoder::new(from_str("0.4e5").unwrap());
2624         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2625         assert_eq!(v, 0.4e5);
2626
2627         let mut decoder = Decoder::new(from_str("0.4e15").unwrap());
2628         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2629         assert_eq!(v, 0.4e15);
2630
2631         let mut decoder = Decoder::new(from_str("0.4e-01").unwrap());
2632         let v: f64 = Decodable::decode(&mut decoder).unwrap();
2633         assert_eq!(v, 0.4e-01);
2634     }
2635
2636     #[test]
2637     fn test_read_str() {
2638         assert_eq!(from_str("\""),    Err(SyntaxError(EOFWhileParsingString, 1, 2)));
2639         assert_eq!(from_str("\"lol"), Err(SyntaxError(EOFWhileParsingString, 1, 5)));
2640
2641         assert_eq!(from_str("\"\""), Ok(String("".to_string())));
2642         assert_eq!(from_str("\"foo\""), Ok(String("foo".to_string())));
2643         assert_eq!(from_str("\"\\\"\""), Ok(String("\"".to_string())));
2644         assert_eq!(from_str("\"\\b\""), Ok(String("\x08".to_string())));
2645         assert_eq!(from_str("\"\\n\""), Ok(String("\n".to_string())));
2646         assert_eq!(from_str("\"\\r\""), Ok(String("\r".to_string())));
2647         assert_eq!(from_str("\"\\t\""), Ok(String("\t".to_string())));
2648         assert_eq!(from_str(" \"foo\" "), Ok(String("foo".to_string())));
2649         assert_eq!(from_str("\"\\u12ab\""), Ok(String("\u12ab".to_string())));
2650         assert_eq!(from_str("\"\\uAB12\""), Ok(String("\uAB12".to_string())));
2651     }
2652
2653     #[test]
2654     fn test_decode_str() {
2655         let s = [("\"\"", ""),
2656                  ("\"foo\"", "foo"),
2657                  ("\"\\\"\"", "\""),
2658                  ("\"\\b\"", "\x08"),
2659                  ("\"\\n\"", "\n"),
2660                  ("\"\\r\"", "\r"),
2661                  ("\"\\t\"", "\t"),
2662                  ("\"\\u12ab\"", "\u12ab"),
2663                  ("\"\\uAB12\"", "\uAB12")];
2664
2665         for &(i, o) in s.iter() {
2666             let mut decoder = Decoder::new(from_str(i).unwrap());
2667             let v: String = Decodable::decode(&mut decoder).unwrap();
2668             assert_eq!(v.as_slice(), o);
2669
2670             let mut decoder = Decoder::new(from_str(i).unwrap());
2671             let v: String = Decodable::decode(&mut decoder).unwrap();
2672             assert_eq!(v, o.to_string());
2673         }
2674     }
2675
2676     #[test]
2677     fn test_read_list() {
2678         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
2679         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingList,  1, 3)));
2680         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
2681         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
2682         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
2683
2684         assert_eq!(from_str("[]"), Ok(List(vec![])));
2685         assert_eq!(from_str("[ ]"), Ok(List(vec![])));
2686         assert_eq!(from_str("[true]"), Ok(List(vec![Boolean(true)])));
2687         assert_eq!(from_str("[ false ]"), Ok(List(vec![Boolean(false)])));
2688         assert_eq!(from_str("[null]"), Ok(List(vec![Null])));
2689         assert_eq!(from_str("[3, 1]"),
2690                      Ok(List(vec![Number(3.0), Number(1.0)])));
2691         assert_eq!(from_str("\n[3, 2]\n"),
2692                      Ok(List(vec![Number(3.0), Number(2.0)])));
2693         assert_eq!(from_str("[2, [4, 1]]"),
2694                Ok(List(vec![Number(2.0), List(vec![Number(4.0), Number(1.0)])])));
2695     }
2696
2697     #[test]
2698     fn test_decode_list() {
2699         let mut decoder = Decoder::new(from_str("[]").unwrap());
2700         let v: Vec<()> = Decodable::decode(&mut decoder).unwrap();
2701         assert_eq!(v, vec![]);
2702
2703         let mut decoder = Decoder::new(from_str("[null]").unwrap());
2704         let v: Vec<()> = Decodable::decode(&mut decoder).unwrap();
2705         assert_eq!(v, vec![()]);
2706
2707         let mut decoder = Decoder::new(from_str("[true]").unwrap());
2708         let v: Vec<bool> = Decodable::decode(&mut decoder).unwrap();
2709         assert_eq!(v, vec![true]);
2710
2711         let mut decoder = Decoder::new(from_str("[true]").unwrap());
2712         let v: Vec<bool> = Decodable::decode(&mut decoder).unwrap();
2713         assert_eq!(v, vec![true]);
2714
2715         let mut decoder = Decoder::new(from_str("[3, 1]").unwrap());
2716         let v: Vec<int> = Decodable::decode(&mut decoder).unwrap();
2717         assert_eq!(v, vec![3, 1]);
2718
2719         let mut decoder = Decoder::new(from_str("[[3], [1, 2]]").unwrap());
2720         let v: Vec<Vec<uint>> = Decodable::decode(&mut decoder).unwrap();
2721         assert_eq!(v, vec![vec![3], vec![1, 2]]);
2722     }
2723
2724     #[test]
2725     fn test_read_object() {
2726         assert_eq!(from_str("{"),       Err(SyntaxError(EOFWhileParsingObject, 1, 2)));
2727         assert_eq!(from_str("{ "),      Err(SyntaxError(EOFWhileParsingObject, 1, 3)));
2728         assert_eq!(from_str("{1"),      Err(SyntaxError(KeyMustBeAString,      1, 2)));
2729         assert_eq!(from_str("{ \"a\""), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
2730         assert_eq!(from_str("{\"a\""),  Err(SyntaxError(EOFWhileParsingObject, 1, 5)));
2731         assert_eq!(from_str("{\"a\" "), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
2732
2733         assert_eq!(from_str("{\"a\" 1"),   Err(SyntaxError(ExpectedColon,         1, 6)));
2734         assert_eq!(from_str("{\"a\":"),    Err(SyntaxError(EOFWhileParsingValue,  1, 6)));
2735         assert_eq!(from_str("{\"a\":1"),   Err(SyntaxError(EOFWhileParsingObject, 1, 7)));
2736         assert_eq!(from_str("{\"a\":1 1"), Err(SyntaxError(InvalidSyntax,         1, 8)));
2737         assert_eq!(from_str("{\"a\":1,"),  Err(SyntaxError(EOFWhileParsingObject, 1, 8)));
2738
2739         assert_eq!(from_str("{}").unwrap(), mk_object([]));
2740         assert_eq!(from_str("{\"a\": 3}").unwrap(),
2741                   mk_object([("a".to_string(), Number(3.0))]));
2742
2743         assert_eq!(from_str(
2744                       "{ \"a\": null, \"b\" : true }").unwrap(),
2745                   mk_object([
2746                       ("a".to_string(), Null),
2747                       ("b".to_string(), Boolean(true))]));
2748         assert_eq!(from_str("\n{ \"a\": null, \"b\" : true }\n").unwrap(),
2749                   mk_object([
2750                       ("a".to_string(), Null),
2751                       ("b".to_string(), Boolean(true))]));
2752         assert_eq!(from_str(
2753                       "{\"a\" : 1.0 ,\"b\": [ true ]}").unwrap(),
2754                   mk_object([
2755                       ("a".to_string(), Number(1.0)),
2756                       ("b".to_string(), List(vec![Boolean(true)]))
2757                   ]));
2758         assert_eq!(from_str(
2759                       "{\
2760                           \"a\": 1.0, \
2761                           \"b\": [\
2762                               true,\
2763                               \"foo\\nbar\", \
2764                               { \"c\": {\"d\": null} } \
2765                           ]\
2766                       }").unwrap(),
2767                   mk_object([
2768                       ("a".to_string(), Number(1.0)),
2769                       ("b".to_string(), List(vec![
2770                           Boolean(true),
2771                           String("foo\nbar".to_string()),
2772                           mk_object([
2773                               ("c".to_string(), mk_object([("d".to_string(), Null)]))
2774                           ])
2775                       ]))
2776                   ]));
2777     }
2778
2779     #[test]
2780     fn test_decode_struct() {
2781         let s = "{
2782             \"inner\": [
2783                 { \"a\": null, \"b\": 2, \"c\": [\"abc\", \"xyz\"] }
2784             ]
2785         }";
2786         let mut decoder = Decoder::new(from_str(s).unwrap());
2787         let v: Outer = Decodable::decode(&mut decoder).unwrap();
2788         assert_eq!(
2789             v,
2790             Outer {
2791                 inner: vec![
2792                     Inner { a: (), b: 2, c: vec!["abc".to_string(), "xyz".to_string()] }
2793                 ]
2794             }
2795         );
2796     }
2797
2798     #[test]
2799     fn test_decode_option() {
2800         let mut decoder = Decoder::new(from_str("null").unwrap());
2801         let value: Option<String> = Decodable::decode(&mut decoder).unwrap();
2802         assert_eq!(value, None);
2803
2804         let mut decoder = Decoder::new(from_str("\"jodhpurs\"").unwrap());
2805         let value: Option<String> = Decodable::decode(&mut decoder).unwrap();
2806         assert_eq!(value, Some("jodhpurs".to_string()));
2807     }
2808
2809     #[test]
2810     fn test_decode_enum() {
2811         let mut decoder = Decoder::new(from_str("\"Dog\"").unwrap());
2812         let value: Animal = Decodable::decode(&mut decoder).unwrap();
2813         assert_eq!(value, Dog);
2814
2815         let s = "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}";
2816         let mut decoder = Decoder::new(from_str(s).unwrap());
2817         let value: Animal = Decodable::decode(&mut decoder).unwrap();
2818         assert_eq!(value, Frog("Henry".to_string(), 349));
2819     }
2820
2821     #[test]
2822     fn test_decode_map() {
2823         let s = "{\"a\": \"Dog\", \"b\": {\"variant\":\"Frog\",\
2824                   \"fields\":[\"Henry\", 349]}}";
2825         let mut decoder = Decoder::new(from_str(s).unwrap());
2826         let mut map: TreeMap<String, Animal> = Decodable::decode(&mut decoder).unwrap();
2827
2828         assert_eq!(map.pop(&"a".to_string()), Some(Dog));
2829         assert_eq!(map.pop(&"b".to_string()), Some(Frog("Henry".to_string(), 349)));
2830     }
2831
2832     #[test]
2833     fn test_multiline_errors() {
2834         assert_eq!(from_str("{\n  \"foo\":\n \"bar\""),
2835             Err(SyntaxError(EOFWhileParsingObject, 3u, 8u)));
2836     }
2837
2838     #[deriving(Decodable)]
2839     struct DecodeStruct {
2840         x: f64,
2841         y: bool,
2842         z: String,
2843         w: Vec<DecodeStruct>
2844     }
2845     #[deriving(Decodable)]
2846     enum DecodeEnum {
2847         A(f64),
2848         B(String)
2849     }
2850     fn check_err<T: Decodable<Decoder, DecoderError>>(to_parse: &'static str,
2851                                                       expected: DecoderError) {
2852         let res: DecodeResult<T> = match from_str(to_parse) {
2853             Err(e) => Err(ParseError(e)),
2854             Ok(json) => Decodable::decode(&mut Decoder::new(json))
2855         };
2856         match res {
2857             Ok(_) => fail!("`{}` parsed & decoded ok, expecting error `{}`",
2858                               to_parse, expected),
2859             Err(ParseError(e)) => fail!("`{}` is not valid json: {}",
2860                                            to_parse, e),
2861             Err(e) => {
2862                 assert_eq!(e, expected);
2863             }
2864         }
2865     }
2866     #[test]
2867     fn test_decode_errors_struct() {
2868         check_err::<DecodeStruct>("[]", ExpectedError("Object".to_string(), "[]".to_string()));
2869         check_err::<DecodeStruct>("{\"x\": true, \"y\": true, \"z\": \"\", \"w\": []}",
2870                                   ExpectedError("Number".to_string(), "true".to_string()));
2871         check_err::<DecodeStruct>("{\"x\": 1, \"y\": [], \"z\": \"\", \"w\": []}",
2872                                   ExpectedError("Boolean".to_string(), "[]".to_string()));
2873         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": {}, \"w\": []}",
2874                                   ExpectedError("String".to_string(), "{}".to_string()));
2875         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\", \"w\": null}",
2876                                   ExpectedError("List".to_string(), "null".to_string()));
2877         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\"}",
2878                                   MissingFieldError("w".to_string()));
2879     }
2880     #[test]
2881     fn test_decode_errors_enum() {
2882         check_err::<DecodeEnum>("{}",
2883                                 MissingFieldError("variant".to_string()));
2884         check_err::<DecodeEnum>("{\"variant\": 1}",
2885                                 ExpectedError("String".to_string(), "1".to_string()));
2886         check_err::<DecodeEnum>("{\"variant\": \"A\"}",
2887                                 MissingFieldError("fields".to_string()));
2888         check_err::<DecodeEnum>("{\"variant\": \"A\", \"fields\": null}",
2889                                 ExpectedError("List".to_string(), "null".to_string()));
2890         check_err::<DecodeEnum>("{\"variant\": \"C\", \"fields\": []}",
2891                                 UnknownVariantError("C".to_string()));
2892     }
2893
2894     #[test]
2895     fn test_find(){
2896         let json_value = from_str("{\"dog\" : \"cat\"}").unwrap();
2897         let found_str = json_value.find(&"dog".to_string());
2898         assert!(found_str.is_some() && found_str.unwrap().as_string().unwrap() == "cat");
2899     }
2900
2901     #[test]
2902     fn test_find_path(){
2903         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
2904         let found_str = json_value.find_path(&[&"dog".to_string(),
2905                                              &"cat".to_string(), &"mouse".to_string()]);
2906         assert!(found_str.is_some() && found_str.unwrap().as_string().unwrap() == "cheese");
2907     }
2908
2909     #[test]
2910     fn test_search(){
2911         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
2912         let found_str = json_value.search(&"mouse".to_string()).and_then(|j| j.as_string());
2913         assert!(found_str.is_some());
2914         assert!(found_str.unwrap() == "cheese");
2915     }
2916
2917     #[test]
2918     fn test_is_object(){
2919         let json_value = from_str("{}").unwrap();
2920         assert!(json_value.is_object());
2921     }
2922
2923     #[test]
2924     fn test_as_object(){
2925         let json_value = from_str("{}").unwrap();
2926         let json_object = json_value.as_object();
2927         assert!(json_object.is_some());
2928     }
2929
2930     #[test]
2931     fn test_is_list(){
2932         let json_value = from_str("[1, 2, 3]").unwrap();
2933         assert!(json_value.is_list());
2934     }
2935
2936     #[test]
2937     fn test_as_list(){
2938         let json_value = from_str("[1, 2, 3]").unwrap();
2939         let json_list = json_value.as_list();
2940         let expected_length = 3;
2941         assert!(json_list.is_some() && json_list.unwrap().len() == expected_length);
2942     }
2943
2944     #[test]
2945     fn test_is_string(){
2946         let json_value = from_str("\"dog\"").unwrap();
2947         assert!(json_value.is_string());
2948     }
2949
2950     #[test]
2951     fn test_as_string(){
2952         let json_value = from_str("\"dog\"").unwrap();
2953         let json_str = json_value.as_string();
2954         let expected_str = "dog";
2955         assert_eq!(json_str, Some(expected_str));
2956     }
2957
2958     #[test]
2959     fn test_is_number(){
2960         let json_value = from_str("12").unwrap();
2961         assert!(json_value.is_number());
2962     }
2963
2964     #[test]
2965     fn test_as_number(){
2966         let json_value = from_str("12").unwrap();
2967         let json_num = json_value.as_number();
2968         let expected_num = 12f64;
2969         assert!(json_num.is_some() && json_num.unwrap() == expected_num);
2970     }
2971
2972     #[test]
2973     fn test_is_boolean(){
2974         let json_value = from_str("false").unwrap();
2975         assert!(json_value.is_boolean());
2976     }
2977
2978     #[test]
2979     fn test_as_boolean(){
2980         let json_value = from_str("false").unwrap();
2981         let json_bool = json_value.as_boolean();
2982         let expected_bool = false;
2983         assert!(json_bool.is_some() && json_bool.unwrap() == expected_bool);
2984     }
2985
2986     #[test]
2987     fn test_is_null(){
2988         let json_value = from_str("null").unwrap();
2989         assert!(json_value.is_null());
2990     }
2991
2992     #[test]
2993     fn test_as_null(){
2994         let json_value = from_str("null").unwrap();
2995         let json_null = json_value.as_null();
2996         let expected_null = ();
2997         assert!(json_null.is_some() && json_null.unwrap() == expected_null);
2998     }
2999
3000     #[test]
3001     fn test_encode_hashmap_with_numeric_key() {
3002         use std::str::from_utf8;
3003         use std::io::Writer;
3004         use std::io::MemWriter;
3005         use collections::HashMap;
3006         let mut hm: HashMap<uint, bool> = HashMap::new();
3007         hm.insert(1, true);
3008         let mut mem_buf = MemWriter::new();
3009         {
3010             let mut encoder = Encoder::new(&mut mem_buf as &mut io::Writer);
3011             hm.encode(&mut encoder).unwrap();
3012         }
3013         let bytes = mem_buf.unwrap();
3014         let json_str = from_utf8(bytes.as_slice()).unwrap();
3015         match from_str(json_str) {
3016             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3017             _ => {} // it parsed and we are good to go
3018         }
3019     }
3020     #[test]
3021     fn test_prettyencode_hashmap_with_numeric_key() {
3022         use std::str::from_utf8;
3023         use std::io::Writer;
3024         use std::io::MemWriter;
3025         use collections::HashMap;
3026         let mut hm: HashMap<uint, bool> = HashMap::new();
3027         hm.insert(1, true);
3028         let mut mem_buf = MemWriter::new();
3029         {
3030             let mut encoder = PrettyEncoder::new(&mut mem_buf as &mut io::Writer);
3031             hm.encode(&mut encoder).unwrap()
3032         }
3033         let bytes = mem_buf.unwrap();
3034         let json_str = from_utf8(bytes.as_slice()).unwrap();
3035         match from_str(json_str) {
3036             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3037             _ => {} // it parsed and we are good to go
3038         }
3039     }
3040     #[test]
3041     fn test_hashmap_with_numeric_key_can_handle_double_quote_delimited_key() {
3042         use collections::HashMap;
3043         use Decodable;
3044         let json_str = "{\"1\":true}";
3045         let json_obj = match from_str(json_str) {
3046             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3047             Ok(o) => o
3048         };
3049         let mut decoder = Decoder::new(json_obj);
3050         let _hm: HashMap<uint, bool> = Decodable::decode(&mut decoder).unwrap();
3051     }
3052
3053     fn assert_stream_equal(src: &str, expected: ~[(JsonEvent, ~[StackElement])]) {
3054         let mut parser = Parser::new(src.chars());
3055         let mut i = 0;
3056         loop {
3057             let evt = match parser.next() {
3058                 Some(e) => e,
3059                 None => { break; }
3060             };
3061             let (ref expected_evt, ref expected_stack) = expected[i];
3062             if !parser.stack().is_equal_to(expected_stack.as_slice()) {
3063                 fail!("Parser stack is not equal to {}", expected_stack);
3064             }
3065             assert_eq!(&evt, expected_evt);
3066             i+=1;
3067         }
3068     }
3069     #[test]
3070     fn test_streaming_parser() {
3071         assert_stream_equal(
3072             r#"{ "foo":"bar", "array" : [0, 1, 2,3 ,4,5], "idents":[null,true,false]}"#,
3073             ~[
3074                 (ObjectStart,             ~[]),
3075                   (StringValue("bar".to_string()),   ~[Key("foo")]),
3076                   (ListStart,             ~[Key("array")]),
3077                     (NumberValue(0.0),    ~[Key("array"), Index(0)]),
3078                     (NumberValue(1.0),    ~[Key("array"), Index(1)]),
3079                     (NumberValue(2.0),    ~[Key("array"), Index(2)]),
3080                     (NumberValue(3.0),    ~[Key("array"), Index(3)]),
3081                     (NumberValue(4.0),    ~[Key("array"), Index(4)]),
3082                     (NumberValue(5.0),    ~[Key("array"), Index(5)]),
3083                   (ListEnd,               ~[Key("array")]),
3084                   (ListStart,             ~[Key("idents")]),
3085                     (NullValue,           ~[Key("idents"), Index(0)]),
3086                     (BooleanValue(true),  ~[Key("idents"), Index(1)]),
3087                     (BooleanValue(false), ~[Key("idents"), Index(2)]),
3088                   (ListEnd,               ~[Key("idents")]),
3089                 (ObjectEnd,               ~[]),
3090             ]
3091         );
3092     }
3093     fn last_event(src: &str) -> JsonEvent {
3094         let mut parser = Parser::new(src.chars());
3095         let mut evt = NullValue;
3096         loop {
3097             evt = match parser.next() {
3098                 Some(e) => e,
3099                 None => return evt,
3100             }
3101         }
3102     }
3103     #[test]
3104     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
3105     fn test_read_object_streaming() {
3106         assert_eq!(last_event("{ "),      Error(SyntaxError(EOFWhileParsingObject, 1, 3)));
3107         assert_eq!(last_event("{1"),      Error(SyntaxError(KeyMustBeAString,      1, 2)));
3108         assert_eq!(last_event("{ \"a\""), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
3109         assert_eq!(last_event("{\"a\""),  Error(SyntaxError(EOFWhileParsingObject, 1, 5)));
3110         assert_eq!(last_event("{\"a\" "), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
3111
3112         assert_eq!(last_event("{\"a\" 1"),   Error(SyntaxError(ExpectedColon,         1, 6)));
3113         assert_eq!(last_event("{\"a\":"),    Error(SyntaxError(EOFWhileParsingValue,  1, 6)));
3114         assert_eq!(last_event("{\"a\":1"),   Error(SyntaxError(EOFWhileParsingObject, 1, 7)));
3115         assert_eq!(last_event("{\"a\":1 1"), Error(SyntaxError(InvalidSyntax,         1, 8)));
3116         assert_eq!(last_event("{\"a\":1,"),  Error(SyntaxError(EOFWhileParsingObject, 1, 8)));
3117
3118         assert_stream_equal(
3119             "{}",
3120             box [(ObjectStart, box []), (ObjectEnd, box [])]
3121         );
3122         assert_stream_equal(
3123             "{\"a\": 3}",
3124             box [
3125                 (ObjectStart,        box []),
3126                   (NumberValue(3.0), box [Key("a")]),
3127                 (ObjectEnd,          box []),
3128             ]
3129         );
3130         assert_stream_equal(
3131             "{ \"a\": null, \"b\" : true }",
3132             box [
3133                 (ObjectStart,           box []),
3134                   (NullValue,           box [Key("a")]),
3135                   (BooleanValue(true),  box [Key("b")]),
3136                 (ObjectEnd,             box []),
3137             ]
3138         );
3139         assert_stream_equal(
3140             "{\"a\" : 1.0 ,\"b\": [ true ]}",
3141             box [
3142                 (ObjectStart,           box []),
3143                   (NumberValue(1.0),    box [Key("a")]),
3144                   (ListStart,           box [Key("b")]),
3145                     (BooleanValue(true),box [Key("b"), Index(0)]),
3146                   (ListEnd,             box [Key("b")]),
3147                 (ObjectEnd,             box []),
3148             ]
3149         );
3150         assert_stream_equal(
3151             r#"{
3152                 "a": 1.0,
3153                 "b": [
3154                     true,
3155                     "foo\nbar",
3156                     { "c": {"d": null} }
3157                 ]
3158             }"#,
3159             ~[
3160                 (ObjectStart,                   ~[]),
3161                   (NumberValue(1.0),            ~[Key("a")]),
3162                   (ListStart,                   ~[Key("b")]),
3163                     (BooleanValue(true),        ~[Key("b"), Index(0)]),
3164                     (StringValue("foo\nbar".to_string()),  ~[Key("b"), Index(1)]),
3165                     (ObjectStart,               ~[Key("b"), Index(2)]),
3166                       (ObjectStart,             ~[Key("b"), Index(2), Key("c")]),
3167                         (NullValue,             ~[Key("b"), Index(2), Key("c"), Key("d")]),
3168                       (ObjectEnd,               ~[Key("b"), Index(2), Key("c")]),
3169                     (ObjectEnd,                 ~[Key("b"), Index(2)]),
3170                   (ListEnd,                     ~[Key("b")]),
3171                 (ObjectEnd,                     ~[]),
3172             ]
3173         );
3174     }
3175     #[test]
3176     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
3177     fn test_read_list_streaming() {
3178         assert_stream_equal(
3179             "[]",
3180             box [
3181                 (ListStart, box []),
3182                 (ListEnd,   box []),
3183             ]
3184         );
3185         assert_stream_equal(
3186             "[ ]",
3187             box [
3188                 (ListStart, box []),
3189                 (ListEnd,   box []),
3190             ]
3191         );
3192         assert_stream_equal(
3193             "[true]",
3194             box [
3195                 (ListStart,              box []),
3196                     (BooleanValue(true), box [Index(0)]),
3197                 (ListEnd,                box []),
3198             ]
3199         );
3200         assert_stream_equal(
3201             "[ false ]",
3202             box [
3203                 (ListStart,               box []),
3204                     (BooleanValue(false), box [Index(0)]),
3205                 (ListEnd,                 box []),
3206             ]
3207         );
3208         assert_stream_equal(
3209             "[null]",
3210             box [
3211                 (ListStart,     box []),
3212                     (NullValue, box [Index(0)]),
3213                 (ListEnd,       box []),
3214             ]
3215         );
3216         assert_stream_equal(
3217             "[3, 1]",
3218             box [
3219                 (ListStart,     box []),
3220                     (NumberValue(3.0), box [Index(0)]),
3221                     (NumberValue(1.0), box [Index(1)]),
3222                 (ListEnd,       box []),
3223             ]
3224         );
3225         assert_stream_equal(
3226             "\n[3, 2]\n",
3227             box [
3228                 (ListStart,     box []),
3229                     (NumberValue(3.0), box [Index(0)]),
3230                     (NumberValue(2.0), box [Index(1)]),
3231                 (ListEnd,       box []),
3232             ]
3233         );
3234         assert_stream_equal(
3235             "[2, [4, 1]]",
3236             box [
3237                 (ListStart,                 box []),
3238                     (NumberValue(2.0),      box [Index(0)]),
3239                     (ListStart,             box [Index(1)]),
3240                         (NumberValue(4.0),  box [Index(1), Index(0)]),
3241                         (NumberValue(1.0),  box [Index(1), Index(1)]),
3242                     (ListEnd,               box [Index(1)]),
3243                 (ListEnd,                   box []),
3244             ]
3245         );
3246
3247         assert_eq!(last_event("["), Error(SyntaxError(EOFWhileParsingValue, 1,  2)));
3248
3249         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
3250         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingList,  1, 3)));
3251         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
3252         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
3253         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
3254
3255     }
3256     #[test]
3257     fn test_trailing_characters_streaming() {
3258         assert_eq!(last_event("nulla"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3259         assert_eq!(last_event("truea"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3260         assert_eq!(last_event("falsea"), Error(SyntaxError(TrailingCharacters, 1, 6)));
3261         assert_eq!(last_event("1a"),     Error(SyntaxError(TrailingCharacters, 1, 2)));
3262         assert_eq!(last_event("[]a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3263         assert_eq!(last_event("{}a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3264     }
3265     #[test]
3266     fn test_read_identifiers_streaming() {
3267         assert_eq!(Parser::new("null".chars()).next(), Some(NullValue));
3268         assert_eq!(Parser::new("true".chars()).next(), Some(BooleanValue(true)));
3269         assert_eq!(Parser::new("false".chars()).next(), Some(BooleanValue(false)));
3270
3271         assert_eq!(last_event("n"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3272         assert_eq!(last_event("nul"),  Error(SyntaxError(InvalidSyntax, 1, 4)));
3273         assert_eq!(last_event("t"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3274         assert_eq!(last_event("truz"), Error(SyntaxError(InvalidSyntax, 1, 4)));
3275         assert_eq!(last_event("f"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3276         assert_eq!(last_event("faz"),  Error(SyntaxError(InvalidSyntax, 1, 3)));
3277     }
3278
3279     #[test]
3280     fn test_stack() {
3281         let mut stack = Stack::new();
3282
3283         assert!(stack.is_empty());
3284         assert!(stack.len() == 0);
3285         assert!(!stack.last_is_index());
3286
3287         stack.push_index(0);
3288         stack.bump_index();
3289
3290         assert!(stack.len() == 1);
3291         assert!(stack.is_equal_to([Index(1)]));
3292         assert!(stack.starts_with([Index(1)]));
3293         assert!(stack.ends_with([Index(1)]));
3294         assert!(stack.last_is_index());
3295         assert!(stack.get(0) == Index(1));
3296
3297         stack.push_key("foo".to_string());
3298
3299         assert!(stack.len() == 2);
3300         assert!(stack.is_equal_to([Index(1), Key("foo")]));
3301         assert!(stack.starts_with([Index(1), Key("foo")]));
3302         assert!(stack.starts_with([Index(1)]));
3303         assert!(stack.ends_with([Index(1), Key("foo")]));
3304         assert!(stack.ends_with([Key("foo")]));
3305         assert!(!stack.last_is_index());
3306         assert!(stack.get(0) == Index(1));
3307         assert!(stack.get(1) == Key("foo"));
3308
3309         stack.push_key("bar".to_string());
3310
3311         assert!(stack.len() == 3);
3312         assert!(stack.is_equal_to([Index(1), Key("foo"), Key("bar")]));
3313         assert!(stack.starts_with([Index(1)]));
3314         assert!(stack.starts_with([Index(1), Key("foo")]));
3315         assert!(stack.starts_with([Index(1), Key("foo"), Key("bar")]));
3316         assert!(stack.ends_with([Key("bar")]));
3317         assert!(stack.ends_with([Key("foo"), Key("bar")]));
3318         assert!(stack.ends_with([Index(1), Key("foo"), Key("bar")]));
3319         assert!(!stack.last_is_index());
3320         assert!(stack.get(0) == Index(1));
3321         assert!(stack.get(1) == Key("foo"));
3322         assert!(stack.get(2) == Key("bar"));
3323
3324         stack.pop();
3325
3326         assert!(stack.len() == 2);
3327         assert!(stack.is_equal_to([Index(1), Key("foo")]));
3328         assert!(stack.starts_with([Index(1), Key("foo")]));
3329         assert!(stack.starts_with([Index(1)]));
3330         assert!(stack.ends_with([Index(1), Key("foo")]));
3331         assert!(stack.ends_with([Key("foo")]));
3332         assert!(!stack.last_is_index());
3333         assert!(stack.get(0) == Index(1));
3334         assert!(stack.get(1) == Key("foo"));
3335     }
3336
3337     #[bench]
3338     fn bench_streaming_small(b: &mut Bencher) {
3339         b.iter( || {
3340             let mut parser = Parser::new(
3341                 r#"{
3342                     "a": 1.0,
3343                     "b": [
3344                         true,
3345                         "foo\nbar",
3346                         { "c": {"d": null} }
3347                     ]
3348                 }"#.chars()
3349             );
3350             loop {
3351                 match parser.next() {
3352                     None => return,
3353                     _ => {}
3354                 }
3355             }
3356         });
3357     }
3358     #[bench]
3359     fn bench_small(b: &mut Bencher) {
3360         b.iter( || {
3361             let _ = from_str(r#"{
3362                 "a": 1.0,
3363                 "b": [
3364                     true,
3365                     "foo\nbar",
3366                     { "c": {"d": null} }
3367                 ]
3368             }"#);
3369         });
3370     }
3371
3372     fn big_json() -> String {
3373         let mut src = "[\n".to_string();
3374         for _ in range(0, 500) {
3375             src.push_str(r#"{ "a": true, "b": null, "c":3.1415, "d": "Hello world", "e": \
3376                             [1,2,3]},"#);
3377         }
3378         src.push_str("{}]");
3379         return src;
3380     }
3381
3382     #[bench]
3383     fn bench_streaming_large(b: &mut Bencher) {
3384         let src = big_json();
3385         b.iter( || {
3386             let mut parser = Parser::new(src.as_slice().chars());
3387             loop {
3388                 match parser.next() {
3389                     None => return,
3390                     _ => {}
3391                 }
3392             }
3393         });
3394     }
3395     #[bench]
3396     fn bench_large(b: &mut Bencher) {
3397         let src = big_json();
3398         b.iter( || { let _ = from_str(src.as_slice()); });
3399     }
3400 }