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