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