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