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