src/libserialize/json.rs

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