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 macro_rules! tuple_impl {
2019     // use variables to indicate the arity of the tuple
2020     ($($tyvar:ident),* ) => {
2021         // the trailing commas are for the 1 tuple
2022         impl<
2023             $( $tyvar : ToJson ),*
2024             > ToJson for ( $( $tyvar ),* , ) {
2025
2026             #[inline]
2027             #[allow(uppercase_variables)]
2028             fn to_json(&self) -> Json {
2029                 match *self {
2030                     ($(ref $tyvar),*,) => List(vec![$($tyvar.to_json()),*])
2031                 }
2032             }
2033         }
2034     }
2035 }
2036
2037 tuple_impl!{A}
2038 tuple_impl!{A, B}
2039 tuple_impl!{A, B, C}
2040 tuple_impl!{A, B, C, D}
2041 tuple_impl!{A, B, C, D, E}
2042 tuple_impl!{A, B, C, D, E, F}
2043 tuple_impl!{A, B, C, D, E, F, G}
2044 tuple_impl!{A, B, C, D, E, F, G, H}
2045 tuple_impl!{A, B, C, D, E, F, G, H, I}
2046 tuple_impl!{A, B, C, D, E, F, G, H, I, J}
2047 tuple_impl!{A, B, C, D, E, F, G, H, I, J, K}
2048 tuple_impl!{A, B, C, D, E, F, G, H, I, J, K, L}
2049
2050 impl<'a, A: ToJson> ToJson for &'a [A] {
2051     fn to_json(&self) -> Json { List(self.iter().map(|elt| elt.to_json()).collect()) }
2052 }
2053
2054 impl<A: ToJson> ToJson for Vec<A> {
2055     fn to_json(&self) -> Json { List(self.iter().map(|elt| elt.to_json()).collect()) }
2056 }
2057
2058 impl<A: ToJson> ToJson for TreeMap<String, A> {
2059     fn to_json(&self) -> Json {
2060         let mut d = TreeMap::new();
2061         for (key, value) in self.iter() {
2062             d.insert((*key).clone(), value.to_json());
2063         }
2064         Object(d)
2065     }
2066 }
2067
2068 impl<A: ToJson> ToJson for HashMap<String, A> {
2069     fn to_json(&self) -> Json {
2070         let mut d = TreeMap::new();
2071         for (key, value) in self.iter() {
2072             d.insert((*key).clone(), value.to_json());
2073         }
2074         Object(d)
2075     }
2076 }
2077
2078 impl<A:ToJson> ToJson for Option<A> {
2079     fn to_json(&self) -> Json {
2080         match *self {
2081             None => Null,
2082             Some(ref value) => value.to_json()
2083         }
2084     }
2085 }
2086
2087 impl fmt::Show for Json {
2088     /// Encodes a json value into a string
2089     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2090         self.to_writer(f).map_err(|_| fmt::WriteError)
2091     }
2092 }
2093
2094 impl std::from_str::FromStr for Json {
2095     fn from_str(s: &str) -> Option<Json> {
2096         from_str(s).ok()
2097     }
2098 }
2099
2100 #[cfg(test)]
2101 mod tests {
2102     extern crate test;
2103     use self::test::Bencher;
2104     use {Encodable, Decodable};
2105     use super::{Encoder, Decoder, Error, Boolean, Number, List, String, Null,
2106                 PrettyEncoder, Object, Json, from_str, ParseError, ExpectedError,
2107                 MissingFieldError, UnknownVariantError, DecodeResult, DecoderError,
2108                 JsonEvent, Parser, StackElement,
2109                 ObjectStart, ObjectEnd, ListStart, ListEnd, BooleanValue, NumberValue, StringValue,
2110                 NullValue, SyntaxError, Key, Index, Stack,
2111                 InvalidSyntax, InvalidNumber, EOFWhileParsingObject, EOFWhileParsingList,
2112                 EOFWhileParsingValue, EOFWhileParsingString, KeyMustBeAString, ExpectedColon,
2113                 TrailingCharacters};
2114     use std::{f32, f64, io};
2115     use std::collections::TreeMap;
2116
2117     #[deriving(PartialEq, Encodable, Decodable, Show)]
2118     enum Animal {
2119         Dog,
2120         Frog(String, int)
2121     }
2122
2123     #[deriving(PartialEq, Encodable, Decodable, Show)]
2124     struct Inner {
2125         a: (),
2126         b: uint,
2127         c: Vec<String>,
2128     }
2129
2130     #[deriving(PartialEq, Encodable, Decodable, Show)]
2131     struct Outer {
2132         inner: Vec<Inner>,
2133     }
2134
2135     fn mk_object(items: &[(String, Json)]) -> Json {
2136         let mut d = TreeMap::new();
2137
2138         for item in items.iter() {
2139             match *item {
2140                 (ref key, ref value) => { d.insert((*key).clone(), (*value).clone()); },
2141             }
2142         };
2143
2144         Object(d)
2145     }
2146
2147     #[test]
2148     fn test_from_str_trait() {
2149         let s = "null";
2150         assert!(::std::from_str::from_str::<Json>(s).unwrap() == from_str(s).unwrap());
2151     }
2152
2153     #[test]
2154     fn test_write_null() {
2155         assert_eq!(Null.to_str().into_string(), "null".to_string());
2156         assert_eq!(Null.to_pretty_str().into_string(), "null".to_string());
2157     }
2158
2159
2160     #[test]
2161     fn test_write_number() {
2162         assert_eq!(Number(3.0).to_str().into_string(), "3".to_string());
2163         assert_eq!(Number(3.0).to_pretty_str().into_string(), "3".to_string());
2164
2165         assert_eq!(Number(3.1).to_str().into_string(), "3.1".to_string());
2166         assert_eq!(Number(3.1).to_pretty_str().into_string(), "3.1".to_string());
2167
2168         assert_eq!(Number(-1.5).to_str().into_string(), "-1.5".to_string());
2169         assert_eq!(Number(-1.5).to_pretty_str().into_string(), "-1.5".to_string());
2170
2171         assert_eq!(Number(0.5).to_str().into_string(), "0.5".to_string());
2172         assert_eq!(Number(0.5).to_pretty_str().into_string(), "0.5".to_string());
2173
2174         assert_eq!(Number(f64::NAN).to_str().into_string(), "null".to_string());
2175         assert_eq!(Number(f64::NAN).to_pretty_str().into_string(), "null".to_string());
2176
2177         assert_eq!(Number(f64::INFINITY).to_str().into_string(), "null".to_string());
2178         assert_eq!(Number(f64::INFINITY).to_pretty_str().into_string(), "null".to_string());
2179
2180         assert_eq!(Number(f64::NEG_INFINITY).to_str().into_string(), "null".to_string());
2181         assert_eq!(Number(f64::NEG_INFINITY).to_pretty_str().into_string(), "null".to_string());
2182     }
2183
2184     #[test]
2185     fn test_write_str() {
2186         assert_eq!(String("".to_string()).to_str().into_string(), "\"\"".to_string());
2187         assert_eq!(String("".to_string()).to_pretty_str().into_string(), "\"\"".to_string());
2188
2189         assert_eq!(String("foo".to_string()).to_str().into_string(), "\"foo\"".to_string());
2190         assert_eq!(String("foo".to_string()).to_pretty_str().into_string(), "\"foo\"".to_string());
2191     }
2192
2193     #[test]
2194     fn test_write_bool() {
2195         assert_eq!(Boolean(true).to_str().into_string(), "true".to_string());
2196         assert_eq!(Boolean(true).to_pretty_str().into_string(), "true".to_string());
2197
2198         assert_eq!(Boolean(false).to_str().into_string(), "false".to_string());
2199         assert_eq!(Boolean(false).to_pretty_str().into_string(), "false".to_string());
2200     }
2201
2202     #[test]
2203     fn test_write_list() {
2204         assert_eq!(List(vec![]).to_str().into_string(), "[]".to_string());
2205         assert_eq!(List(vec![]).to_pretty_str().into_string(), "[]".to_string());
2206
2207         assert_eq!(List(vec![Boolean(true)]).to_str().into_string(), "[true]".to_string());
2208         assert_eq!(
2209             List(vec![Boolean(true)]).to_pretty_str().into_string(),
2210             "\
2211             [\n  \
2212                 true\n\
2213             ]".to_string()
2214         );
2215
2216         let long_test_list = List(vec![
2217             Boolean(false),
2218             Null,
2219             List(vec![String("foo\nbar".to_string()), Number(3.5)])]);
2220
2221         assert_eq!(long_test_list.to_str().into_string(),
2222             "[false,null,[\"foo\\nbar\",3.5]]".to_string());
2223         assert_eq!(
2224             long_test_list.to_pretty_str().into_string(),
2225             "\
2226             [\n  \
2227                 false,\n  \
2228                 null,\n  \
2229                 [\n    \
2230                     \"foo\\nbar\",\n    \
2231                     3.5\n  \
2232                 ]\n\
2233             ]".to_string()
2234         );
2235     }
2236
2237     #[test]
2238     fn test_write_object() {
2239         assert_eq!(mk_object([]).to_str().into_string(), "{}".to_string());
2240         assert_eq!(mk_object([]).to_pretty_str().into_string(), "{}".to_string());
2241
2242         assert_eq!(
2243             mk_object([
2244                 ("a".to_string(), Boolean(true))
2245             ]).to_str().into_string(),
2246             "{\"a\":true}".to_string()
2247         );
2248         assert_eq!(
2249             mk_object([("a".to_string(), Boolean(true))]).to_pretty_str(),
2250             "\
2251             {\n  \
2252                 \"a\": true\n\
2253             }".to_string()
2254         );
2255
2256         let complex_obj = mk_object([
2257                 ("b".to_string(), List(vec![
2258                     mk_object([("c".to_string(), String("\x0c\r".to_string()))]),
2259                     mk_object([("d".to_string(), String("".to_string()))])
2260                 ]))
2261             ]);
2262
2263         assert_eq!(
2264             complex_obj.to_str().into_string(),
2265             "{\
2266                 \"b\":[\
2267                     {\"c\":\"\\f\\r\"},\
2268                     {\"d\":\"\"}\
2269                 ]\
2270             }".to_string()
2271         );
2272         assert_eq!(
2273             complex_obj.to_pretty_str().into_string(),
2274             "\
2275             {\n  \
2276                 \"b\": [\n    \
2277                     {\n      \
2278                         \"c\": \"\\f\\r\"\n    \
2279                     },\n    \
2280                     {\n      \
2281                         \"d\": \"\"\n    \
2282                     }\n  \
2283                 ]\n\
2284             }".to_string()
2285         );
2286
2287         let a = mk_object([
2288             ("a".to_string(), Boolean(true)),
2289             ("b".to_string(), List(vec![
2290                 mk_object([("c".to_string(), String("\x0c\r".to_string()))]),
2291                 mk_object([("d".to_string(), String("".to_string()))])
2292             ]))
2293         ]);
2294
2295         // We can't compare the strings directly because the object fields be
2296         // printed in a different order.
2297         assert_eq!(a.clone(), from_str(a.to_str().as_slice()).unwrap());
2298         assert_eq!(a.clone(),
2299                    from_str(a.to_pretty_str().as_slice()).unwrap());
2300     }
2301
2302     fn with_str_writer(f: |&mut io::Writer|) -> String {
2303         use std::io::MemWriter;
2304         use std::str;
2305
2306         let mut m = MemWriter::new();
2307         f(&mut m as &mut io::Writer);
2308         str::from_utf8(m.unwrap().as_slice()).unwrap().to_string()
2309     }
2310
2311     #[test]
2312     fn test_write_enum() {
2313         let animal = Dog;
2314         assert_eq!(
2315             with_str_writer(|writer| {
2316                 let mut encoder = Encoder::new(writer);
2317                 animal.encode(&mut encoder).unwrap();
2318             }),
2319             "\"Dog\"".to_string()
2320         );
2321         assert_eq!(
2322             with_str_writer(|writer| {
2323                 let mut encoder = PrettyEncoder::new(writer);
2324                 animal.encode(&mut encoder).unwrap();
2325             }),
2326             "\"Dog\"".to_string()
2327         );
2328
2329         let animal = Frog("Henry".to_string(), 349);
2330         assert_eq!(
2331             with_str_writer(|writer| {
2332                 let mut encoder = Encoder::new(writer);
2333                 animal.encode(&mut encoder).unwrap();
2334             }),
2335             "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}".to_string()
2336         );
2337         assert_eq!(
2338             with_str_writer(|writer| {
2339                 let mut encoder = PrettyEncoder::new(writer);
2340                 animal.encode(&mut encoder).unwrap();
2341             }),
2342             "\
2343             [\n  \
2344                 \"Frog\",\n  \
2345                 \"Henry\",\n  \
2346                 349\n\
2347             ]".to_string()
2348         );
2349     }
2350
2351     #[test]
2352     fn test_write_some() {
2353         let value = Some("jodhpurs".to_string());
2354         let s = with_str_writer(|writer| {
2355             let mut encoder = Encoder::new(writer);
2356             value.encode(&mut encoder).unwrap();
2357         });
2358         assert_eq!(s, "\"jodhpurs\"".to_string());
2359
2360         let value = Some("jodhpurs".to_string());
2361         let s = with_str_writer(|writer| {
2362             let mut encoder = PrettyEncoder::new(writer);
2363             value.encode(&mut encoder).unwrap();
2364         });
2365         assert_eq!(s, "\"jodhpurs\"".to_string());
2366     }
2367
2368     #[test]
2369     fn test_write_none() {
2370         let value: Option<String> = None;
2371         let s = with_str_writer(|writer| {
2372             let mut encoder = Encoder::new(writer);
2373             value.encode(&mut encoder).unwrap();
2374         });
2375         assert_eq!(s, "null".to_string());
2376
2377         let s = with_str_writer(|writer| {
2378             let mut encoder = Encoder::new(writer);
2379             value.encode(&mut encoder).unwrap();
2380         });
2381         assert_eq!(s, "null".to_string());
2382     }
2383
2384     #[test]
2385     fn test_trailing_characters() {
2386         assert_eq!(from_str("nulla"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2387         assert_eq!(from_str("truea"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2388         assert_eq!(from_str("falsea"), Err(SyntaxError(TrailingCharacters, 1, 6)));
2389         assert_eq!(from_str("1a"),     Err(SyntaxError(TrailingCharacters, 1, 2)));
2390         assert_eq!(from_str("[]a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2391         assert_eq!(from_str("{}a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2392     }
2393
2394     #[test]
2395     fn test_read_identifiers() {
2396         assert_eq!(from_str("n"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2397         assert_eq!(from_str("nul"),  Err(SyntaxError(InvalidSyntax, 1, 4)));
2398         assert_eq!(from_str("t"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2399         assert_eq!(from_str("truz"), Err(SyntaxError(InvalidSyntax, 1, 4)));
2400         assert_eq!(from_str("f"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2401         assert_eq!(from_str("faz"),  Err(SyntaxError(InvalidSyntax, 1, 3)));
2402
2403         assert_eq!(from_str("null"), Ok(Null));
2404         assert_eq!(from_str("true"), Ok(Boolean(true)));
2405         assert_eq!(from_str("false"), Ok(Boolean(false)));
2406         assert_eq!(from_str(" null "), Ok(Null));
2407         assert_eq!(from_str(" true "), Ok(Boolean(true)));
2408         assert_eq!(from_str(" false "), Ok(Boolean(false)));
2409     }
2410
2411     #[test]
2412     fn test_decode_identifiers() {
2413         let v: () = super::decode("null").unwrap();
2414         assert_eq!(v, ());
2415
2416         let v: bool = super::decode("true").unwrap();
2417         assert_eq!(v, true);
2418
2419         let v: bool = super::decode("false").unwrap();
2420         assert_eq!(v, false);
2421     }
2422
2423     #[test]
2424     fn test_read_number() {
2425         assert_eq!(from_str("+"),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2426         assert_eq!(from_str("."),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2427         assert_eq!(from_str("NaN"), Err(SyntaxError(InvalidSyntax, 1, 1)));
2428         assert_eq!(from_str("-"),   Err(SyntaxError(InvalidNumber, 1, 2)));
2429         assert_eq!(from_str("00"),  Err(SyntaxError(InvalidNumber, 1, 2)));
2430         assert_eq!(from_str("1."),  Err(SyntaxError(InvalidNumber, 1, 3)));
2431         assert_eq!(from_str("1e"),  Err(SyntaxError(InvalidNumber, 1, 3)));
2432         assert_eq!(from_str("1e+"), Err(SyntaxError(InvalidNumber, 1, 4)));
2433
2434         assert_eq!(from_str("3"), Ok(Number(3.0)));
2435         assert_eq!(from_str("3.1"), Ok(Number(3.1)));
2436         assert_eq!(from_str("-1.2"), Ok(Number(-1.2)));
2437         assert_eq!(from_str("0.4"), Ok(Number(0.4)));
2438         assert_eq!(from_str("0.4e5"), Ok(Number(0.4e5)));
2439         assert_eq!(from_str("0.4e+15"), Ok(Number(0.4e15)));
2440         assert_eq!(from_str("0.4e-01"), Ok(Number(0.4e-01)));
2441         assert_eq!(from_str(" 3 "), Ok(Number(3.0)));
2442     }
2443
2444     #[test]
2445     fn test_decode_numbers() {
2446         let v: f64 = super::decode("3").unwrap();
2447         assert_eq!(v, 3.0);
2448
2449         let v: f64 = super::decode("3.1").unwrap();
2450         assert_eq!(v, 3.1);
2451
2452         let v: f64 = super::decode("-1.2").unwrap();
2453         assert_eq!(v, -1.2);
2454
2455         let v: f64 = super::decode("0.4").unwrap();
2456         assert_eq!(v, 0.4);
2457
2458         let v: f64 = super::decode("0.4e5").unwrap();
2459         assert_eq!(v, 0.4e5);
2460
2461         let v: f64 = super::decode("0.4e15").unwrap();
2462         assert_eq!(v, 0.4e15);
2463
2464         let v: f64 = super::decode("0.4e-01").unwrap();
2465         assert_eq!(v, 0.4e-01);
2466     }
2467
2468     #[test]
2469     fn test_read_str() {
2470         assert_eq!(from_str("\""),    Err(SyntaxError(EOFWhileParsingString, 1, 2)));
2471         assert_eq!(from_str("\"lol"), Err(SyntaxError(EOFWhileParsingString, 1, 5)));
2472
2473         assert_eq!(from_str("\"\""), Ok(String("".to_string())));
2474         assert_eq!(from_str("\"foo\""), Ok(String("foo".to_string())));
2475         assert_eq!(from_str("\"\\\"\""), Ok(String("\"".to_string())));
2476         assert_eq!(from_str("\"\\b\""), Ok(String("\x08".to_string())));
2477         assert_eq!(from_str("\"\\n\""), Ok(String("\n".to_string())));
2478         assert_eq!(from_str("\"\\r\""), Ok(String("\r".to_string())));
2479         assert_eq!(from_str("\"\\t\""), Ok(String("\t".to_string())));
2480         assert_eq!(from_str(" \"foo\" "), Ok(String("foo".to_string())));
2481         assert_eq!(from_str("\"\\u12ab\""), Ok(String("\u12ab".to_string())));
2482         assert_eq!(from_str("\"\\uAB12\""), Ok(String("\uAB12".to_string())));
2483     }
2484
2485     #[test]
2486     fn test_decode_str() {
2487         let s = [("\"\"", ""),
2488                  ("\"foo\"", "foo"),
2489                  ("\"\\\"\"", "\""),
2490                  ("\"\\b\"", "\x08"),
2491                  ("\"\\n\"", "\n"),
2492                  ("\"\\r\"", "\r"),
2493                  ("\"\\t\"", "\t"),
2494                  ("\"\\u12ab\"", "\u12ab"),
2495                  ("\"\\uAB12\"", "\uAB12")];
2496
2497         for &(i, o) in s.iter() {
2498             let v: String = super::decode(i).unwrap();
2499             assert_eq!(v.as_slice(), o);
2500         }
2501     }
2502
2503     #[test]
2504     fn test_read_list() {
2505         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
2506         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingList,  1, 3)));
2507         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
2508         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
2509         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
2510
2511         assert_eq!(from_str("[]"), Ok(List(vec![])));
2512         assert_eq!(from_str("[ ]"), Ok(List(vec![])));
2513         assert_eq!(from_str("[true]"), Ok(List(vec![Boolean(true)])));
2514         assert_eq!(from_str("[ false ]"), Ok(List(vec![Boolean(false)])));
2515         assert_eq!(from_str("[null]"), Ok(List(vec![Null])));
2516         assert_eq!(from_str("[3, 1]"),
2517                      Ok(List(vec![Number(3.0), Number(1.0)])));
2518         assert_eq!(from_str("\n[3, 2]\n"),
2519                      Ok(List(vec![Number(3.0), Number(2.0)])));
2520         assert_eq!(from_str("[2, [4, 1]]"),
2521                Ok(List(vec![Number(2.0), List(vec![Number(4.0), Number(1.0)])])));
2522     }
2523
2524     #[test]
2525     fn test_decode_list() {
2526         let v: Vec<()> = super::decode("[]").unwrap();
2527         assert_eq!(v, vec![]);
2528
2529         let v: Vec<()> = super::decode("[null]").unwrap();
2530         assert_eq!(v, vec![()]);
2531
2532         let v: Vec<bool> = super::decode("[true]").unwrap();
2533         assert_eq!(v, vec![true]);
2534
2535         let v: Vec<int> = super::decode("[3, 1]").unwrap();
2536         assert_eq!(v, vec![3, 1]);
2537
2538         let v: Vec<Vec<uint>> = super::decode("[[3], [1, 2]]").unwrap();
2539         assert_eq!(v, vec![vec![3], vec![1, 2]]);
2540     }
2541
2542     #[test]
2543     fn test_read_object() {
2544         assert_eq!(from_str("{"),       Err(SyntaxError(EOFWhileParsingObject, 1, 2)));
2545         assert_eq!(from_str("{ "),      Err(SyntaxError(EOFWhileParsingObject, 1, 3)));
2546         assert_eq!(from_str("{1"),      Err(SyntaxError(KeyMustBeAString,      1, 2)));
2547         assert_eq!(from_str("{ \"a\""), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
2548         assert_eq!(from_str("{\"a\""),  Err(SyntaxError(EOFWhileParsingObject, 1, 5)));
2549         assert_eq!(from_str("{\"a\" "), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
2550
2551         assert_eq!(from_str("{\"a\" 1"),   Err(SyntaxError(ExpectedColon,         1, 6)));
2552         assert_eq!(from_str("{\"a\":"),    Err(SyntaxError(EOFWhileParsingValue,  1, 6)));
2553         assert_eq!(from_str("{\"a\":1"),   Err(SyntaxError(EOFWhileParsingObject, 1, 7)));
2554         assert_eq!(from_str("{\"a\":1 1"), Err(SyntaxError(InvalidSyntax,         1, 8)));
2555         assert_eq!(from_str("{\"a\":1,"),  Err(SyntaxError(EOFWhileParsingObject, 1, 8)));
2556
2557         assert_eq!(from_str("{}").unwrap(), mk_object([]));
2558         assert_eq!(from_str("{\"a\": 3}").unwrap(),
2559                   mk_object([("a".to_string(), Number(3.0))]));
2560
2561         assert_eq!(from_str(
2562                       "{ \"a\": null, \"b\" : true }").unwrap(),
2563                   mk_object([
2564                       ("a".to_string(), Null),
2565                       ("b".to_string(), Boolean(true))]));
2566         assert_eq!(from_str("\n{ \"a\": null, \"b\" : true }\n").unwrap(),
2567                   mk_object([
2568                       ("a".to_string(), Null),
2569                       ("b".to_string(), Boolean(true))]));
2570         assert_eq!(from_str(
2571                       "{\"a\" : 1.0 ,\"b\": [ true ]}").unwrap(),
2572                   mk_object([
2573                       ("a".to_string(), Number(1.0)),
2574                       ("b".to_string(), List(vec![Boolean(true)]))
2575                   ]));
2576         assert_eq!(from_str(
2577                       "{\
2578                           \"a\": 1.0, \
2579                           \"b\": [\
2580                               true,\
2581                               \"foo\\nbar\", \
2582                               { \"c\": {\"d\": null} } \
2583                           ]\
2584                       }").unwrap(),
2585                   mk_object([
2586                       ("a".to_string(), Number(1.0)),
2587                       ("b".to_string(), List(vec![
2588                           Boolean(true),
2589                           String("foo\nbar".to_string()),
2590                           mk_object([
2591                               ("c".to_string(), mk_object([("d".to_string(), Null)]))
2592                           ])
2593                       ]))
2594                   ]));
2595     }
2596
2597     #[test]
2598     fn test_decode_struct() {
2599         let s = "{
2600             \"inner\": [
2601                 { \"a\": null, \"b\": 2, \"c\": [\"abc\", \"xyz\"] }
2602             ]
2603         }";
2604
2605         let v: Outer = super::decode(s).unwrap();
2606         assert_eq!(
2607             v,
2608             Outer {
2609                 inner: vec![
2610                     Inner { a: (), b: 2, c: vec!["abc".to_string(), "xyz".to_string()] }
2611                 ]
2612             }
2613         );
2614     }
2615
2616     #[deriving(Decodable)]
2617     struct FloatStruct {
2618         f: f64,
2619         a: Vec<f64>
2620     }
2621     #[test]
2622     fn test_decode_struct_with_nan() {
2623         let s = "{\"f\":null,\"a\":[null,123]}";
2624         let obj: FloatStruct = super::decode(s).unwrap();
2625         assert!(obj.f.is_nan());
2626         assert!(obj.a.get(0).is_nan());
2627         assert_eq!(obj.a.get(1), &123f64);
2628     }
2629
2630     #[test]
2631     fn test_decode_option() {
2632         let value: Option<String> = super::decode("null").unwrap();
2633         assert_eq!(value, None);
2634
2635         let value: Option<String> = super::decode("\"jodhpurs\"").unwrap();
2636         assert_eq!(value, Some("jodhpurs".to_string()));
2637     }
2638
2639     #[test]
2640     fn test_decode_enum() {
2641         let value: Animal = super::decode("\"Dog\"").unwrap();
2642         assert_eq!(value, Dog);
2643
2644         let s = "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}";
2645         let value: Animal = super::decode(s).unwrap();
2646         assert_eq!(value, Frog("Henry".to_string(), 349));
2647     }
2648
2649     #[test]
2650     fn test_decode_map() {
2651         let s = "{\"a\": \"Dog\", \"b\": {\"variant\":\"Frog\",\
2652                   \"fields\":[\"Henry\", 349]}}";
2653         let mut map: TreeMap<String, Animal> = super::decode(s).unwrap();
2654
2655         assert_eq!(map.pop(&"a".to_string()), Some(Dog));
2656         assert_eq!(map.pop(&"b".to_string()), Some(Frog("Henry".to_string(), 349)));
2657     }
2658
2659     #[test]
2660     fn test_multiline_errors() {
2661         assert_eq!(from_str("{\n  \"foo\":\n \"bar\""),
2662             Err(SyntaxError(EOFWhileParsingObject, 3u, 8u)));
2663     }
2664
2665     #[deriving(Decodable)]
2666     #[allow(dead_code)]
2667     struct DecodeStruct {
2668         x: f64,
2669         y: bool,
2670         z: String,
2671         w: Vec<DecodeStruct>
2672     }
2673     #[deriving(Decodable)]
2674     enum DecodeEnum {
2675         A(f64),
2676         B(String)
2677     }
2678     fn check_err<T: Decodable<Decoder, DecoderError>>(to_parse: &'static str,
2679                                                       expected: DecoderError) {
2680         let res: DecodeResult<T> = match from_str(to_parse) {
2681             Err(e) => Err(ParseError(e)),
2682             Ok(json) => Decodable::decode(&mut Decoder::new(json))
2683         };
2684         match res {
2685             Ok(_) => fail!("`{}` parsed & decoded ok, expecting error `{}`",
2686                               to_parse, expected),
2687             Err(ParseError(e)) => fail!("`{}` is not valid json: {}",
2688                                            to_parse, e),
2689             Err(e) => {
2690                 assert_eq!(e, expected);
2691             }
2692         }
2693     }
2694     #[test]
2695     fn test_decode_errors_struct() {
2696         check_err::<DecodeStruct>("[]", ExpectedError("Object".to_string(), "[]".to_string()));
2697         check_err::<DecodeStruct>("{\"x\": true, \"y\": true, \"z\": \"\", \"w\": []}",
2698                                   ExpectedError("Number".to_string(), "true".to_string()));
2699         check_err::<DecodeStruct>("{\"x\": 1, \"y\": [], \"z\": \"\", \"w\": []}",
2700                                   ExpectedError("Boolean".to_string(), "[]".to_string()));
2701         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": {}, \"w\": []}",
2702                                   ExpectedError("String".to_string(), "{}".to_string()));
2703         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\", \"w\": null}",
2704                                   ExpectedError("List".to_string(), "null".to_string()));
2705         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\"}",
2706                                   MissingFieldError("w".to_string()));
2707     }
2708     #[test]
2709     fn test_decode_errors_enum() {
2710         check_err::<DecodeEnum>("{}",
2711                                 MissingFieldError("variant".to_string()));
2712         check_err::<DecodeEnum>("{\"variant\": 1}",
2713                                 ExpectedError("String".to_string(), "1".to_string()));
2714         check_err::<DecodeEnum>("{\"variant\": \"A\"}",
2715                                 MissingFieldError("fields".to_string()));
2716         check_err::<DecodeEnum>("{\"variant\": \"A\", \"fields\": null}",
2717                                 ExpectedError("List".to_string(), "null".to_string()));
2718         check_err::<DecodeEnum>("{\"variant\": \"C\", \"fields\": []}",
2719                                 UnknownVariantError("C".to_string()));
2720     }
2721
2722     #[test]
2723     fn test_find(){
2724         let json_value = from_str("{\"dog\" : \"cat\"}").unwrap();
2725         let found_str = json_value.find(&"dog".to_string());
2726         assert!(found_str.is_some() && found_str.unwrap().as_string().unwrap() == "cat");
2727     }
2728
2729     #[test]
2730     fn test_find_path(){
2731         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
2732         let found_str = json_value.find_path(&[&"dog".to_string(),
2733                                              &"cat".to_string(), &"mouse".to_string()]);
2734         assert!(found_str.is_some() && found_str.unwrap().as_string().unwrap() == "cheese");
2735     }
2736
2737     #[test]
2738     fn test_search(){
2739         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
2740         let found_str = json_value.search(&"mouse".to_string()).and_then(|j| j.as_string());
2741         assert!(found_str.is_some());
2742         assert!(found_str.unwrap() == "cheese");
2743     }
2744
2745     #[test]
2746     fn test_is_object(){
2747         let json_value = from_str("{}").unwrap();
2748         assert!(json_value.is_object());
2749     }
2750
2751     #[test]
2752     fn test_as_object(){
2753         let json_value = from_str("{}").unwrap();
2754         let json_object = json_value.as_object();
2755         assert!(json_object.is_some());
2756     }
2757
2758     #[test]
2759     fn test_is_list(){
2760         let json_value = from_str("[1, 2, 3]").unwrap();
2761         assert!(json_value.is_list());
2762     }
2763
2764     #[test]
2765     fn test_as_list(){
2766         let json_value = from_str("[1, 2, 3]").unwrap();
2767         let json_list = json_value.as_list();
2768         let expected_length = 3;
2769         assert!(json_list.is_some() && json_list.unwrap().len() == expected_length);
2770     }
2771
2772     #[test]
2773     fn test_is_string(){
2774         let json_value = from_str("\"dog\"").unwrap();
2775         assert!(json_value.is_string());
2776     }
2777
2778     #[test]
2779     fn test_as_string(){
2780         let json_value = from_str("\"dog\"").unwrap();
2781         let json_str = json_value.as_string();
2782         let expected_str = "dog";
2783         assert_eq!(json_str, Some(expected_str));
2784     }
2785
2786     #[test]
2787     fn test_is_number(){
2788         let json_value = from_str("12").unwrap();
2789         assert!(json_value.is_number());
2790     }
2791
2792     #[test]
2793     fn test_as_number(){
2794         let json_value = from_str("12").unwrap();
2795         let json_num = json_value.as_number();
2796         let expected_num = 12f64;
2797         assert!(json_num.is_some() && json_num.unwrap() == expected_num);
2798     }
2799
2800     #[test]
2801     fn test_is_boolean(){
2802         let json_value = from_str("false").unwrap();
2803         assert!(json_value.is_boolean());
2804     }
2805
2806     #[test]
2807     fn test_as_boolean(){
2808         let json_value = from_str("false").unwrap();
2809         let json_bool = json_value.as_boolean();
2810         let expected_bool = false;
2811         assert!(json_bool.is_some() && json_bool.unwrap() == expected_bool);
2812     }
2813
2814     #[test]
2815     fn test_is_null(){
2816         let json_value = from_str("null").unwrap();
2817         assert!(json_value.is_null());
2818     }
2819
2820     #[test]
2821     fn test_as_null(){
2822         let json_value = from_str("null").unwrap();
2823         let json_null = json_value.as_null();
2824         let expected_null = ();
2825         assert!(json_null.is_some() && json_null.unwrap() == expected_null);
2826     }
2827
2828     #[test]
2829     fn test_encode_hashmap_with_numeric_key() {
2830         use std::str::from_utf8;
2831         use std::io::Writer;
2832         use std::io::MemWriter;
2833         use std::collections::HashMap;
2834         let mut hm: HashMap<uint, bool> = HashMap::new();
2835         hm.insert(1, true);
2836         let mut mem_buf = MemWriter::new();
2837         {
2838             let mut encoder = Encoder::new(&mut mem_buf as &mut io::Writer);
2839             hm.encode(&mut encoder).unwrap();
2840         }
2841         let bytes = mem_buf.unwrap();
2842         let json_str = from_utf8(bytes.as_slice()).unwrap();
2843         match from_str(json_str) {
2844             Err(_) => fail!("Unable to parse json_str: {}", json_str),
2845             _ => {} // it parsed and we are good to go
2846         }
2847     }
2848     #[test]
2849     fn test_prettyencode_hashmap_with_numeric_key() {
2850         use std::str::from_utf8;
2851         use std::io::Writer;
2852         use std::io::MemWriter;
2853         use std::collections::HashMap;
2854         let mut hm: HashMap<uint, bool> = HashMap::new();
2855         hm.insert(1, true);
2856         let mut mem_buf = MemWriter::new();
2857         {
2858             let mut encoder = PrettyEncoder::new(&mut mem_buf as &mut io::Writer);
2859             hm.encode(&mut encoder).unwrap()
2860         }
2861         let bytes = mem_buf.unwrap();
2862         let json_str = from_utf8(bytes.as_slice()).unwrap();
2863         match from_str(json_str) {
2864             Err(_) => fail!("Unable to parse json_str: {}", json_str),
2865             _ => {} // it parsed and we are good to go
2866         }
2867     }
2868     #[test]
2869     fn test_hashmap_with_numeric_key_can_handle_double_quote_delimited_key() {
2870         use std::collections::HashMap;
2871         use Decodable;
2872         let json_str = "{\"1\":true}";
2873         let json_obj = match from_str(json_str) {
2874             Err(_) => fail!("Unable to parse json_str: {}", json_str),
2875             Ok(o) => o
2876         };
2877         let mut decoder = Decoder::new(json_obj);
2878         let _hm: HashMap<uint, bool> = Decodable::decode(&mut decoder).unwrap();
2879     }
2880
2881     fn assert_stream_equal(src: &str,
2882                            expected: Vec<(JsonEvent, Vec<StackElement>)>) {
2883         let mut parser = Parser::new(src.chars());
2884         let mut i = 0;
2885         loop {
2886             let evt = match parser.next() {
2887                 Some(e) => e,
2888                 None => { break; }
2889             };
2890             let (ref expected_evt, ref expected_stack) = *expected.get(i);
2891             if !parser.stack().is_equal_to(expected_stack.as_slice()) {
2892                 fail!("Parser stack is not equal to {}", expected_stack);
2893             }
2894             assert_eq!(&evt, expected_evt);
2895             i+=1;
2896         }
2897     }
2898     #[test]
2899     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
2900     fn test_streaming_parser() {
2901         assert_stream_equal(
2902             r#"{ "foo":"bar", "array" : [0, 1, 2,3 ,4,5], "idents":[null,true,false]}"#,
2903             vec![
2904                 (ObjectStart,             vec![]),
2905                   (StringValue("bar".to_string()),   vec![Key("foo")]),
2906                   (ListStart,             vec![Key("array")]),
2907                     (NumberValue(0.0),    vec![Key("array"), Index(0)]),
2908                     (NumberValue(1.0),    vec![Key("array"), Index(1)]),
2909                     (NumberValue(2.0),    vec![Key("array"), Index(2)]),
2910                     (NumberValue(3.0),    vec![Key("array"), Index(3)]),
2911                     (NumberValue(4.0),    vec![Key("array"), Index(4)]),
2912                     (NumberValue(5.0),    vec![Key("array"), Index(5)]),
2913                   (ListEnd,               vec![Key("array")]),
2914                   (ListStart,             vec![Key("idents")]),
2915                     (NullValue,           vec![Key("idents"), Index(0)]),
2916                     (BooleanValue(true),  vec![Key("idents"), Index(1)]),
2917                     (BooleanValue(false), vec![Key("idents"), Index(2)]),
2918                   (ListEnd,               vec![Key("idents")]),
2919                 (ObjectEnd,               vec![]),
2920             ]
2921         );
2922     }
2923     fn last_event(src: &str) -> JsonEvent {
2924         let mut parser = Parser::new(src.chars());
2925         let mut evt = NullValue;
2926         loop {
2927             evt = match parser.next() {
2928                 Some(e) => e,
2929                 None => return evt,
2930             }
2931         }
2932     }
2933     #[test]
2934     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
2935     fn test_read_object_streaming() {
2936         assert_eq!(last_event("{ "),      Error(SyntaxError(EOFWhileParsingObject, 1, 3)));
2937         assert_eq!(last_event("{1"),      Error(SyntaxError(KeyMustBeAString,      1, 2)));
2938         assert_eq!(last_event("{ \"a\""), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
2939         assert_eq!(last_event("{\"a\""),  Error(SyntaxError(EOFWhileParsingObject, 1, 5)));
2940         assert_eq!(last_event("{\"a\" "), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
2941
2942         assert_eq!(last_event("{\"a\" 1"),   Error(SyntaxError(ExpectedColon,         1, 6)));
2943         assert_eq!(last_event("{\"a\":"),    Error(SyntaxError(EOFWhileParsingValue,  1, 6)));
2944         assert_eq!(last_event("{\"a\":1"),   Error(SyntaxError(EOFWhileParsingObject, 1, 7)));
2945         assert_eq!(last_event("{\"a\":1 1"), Error(SyntaxError(InvalidSyntax,         1, 8)));
2946         assert_eq!(last_event("{\"a\":1,"),  Error(SyntaxError(EOFWhileParsingObject, 1, 8)));
2947
2948         assert_stream_equal(
2949             "{}",
2950             vec![(ObjectStart, vec![]), (ObjectEnd, vec![])]
2951         );
2952         assert_stream_equal(
2953             "{\"a\": 3}",
2954             vec![
2955                 (ObjectStart,        vec![]),
2956                   (NumberValue(3.0), vec![Key("a")]),
2957                 (ObjectEnd,          vec![]),
2958             ]
2959         );
2960         assert_stream_equal(
2961             "{ \"a\": null, \"b\" : true }",
2962             vec![
2963                 (ObjectStart,           vec![]),
2964                   (NullValue,           vec![Key("a")]),
2965                   (BooleanValue(true),  vec![Key("b")]),
2966                 (ObjectEnd,             vec![]),
2967             ]
2968         );
2969         assert_stream_equal(
2970             "{\"a\" : 1.0 ,\"b\": [ true ]}",
2971             vec![
2972                 (ObjectStart,           vec![]),
2973                   (NumberValue(1.0),    vec![Key("a")]),
2974                   (ListStart,           vec![Key("b")]),
2975                     (BooleanValue(true),vec![Key("b"), Index(0)]),
2976                   (ListEnd,             vec![Key("b")]),
2977                 (ObjectEnd,             vec![]),
2978             ]
2979         );
2980         assert_stream_equal(
2981             r#"{
2982                 "a": 1.0,
2983                 "b": [
2984                     true,
2985                     "foo\nbar",
2986                     { "c": {"d": null} }
2987                 ]
2988             }"#,
2989             vec![
2990                 (ObjectStart,                   vec![]),
2991                   (NumberValue(1.0),            vec![Key("a")]),
2992                   (ListStart,                   vec![Key("b")]),
2993                     (BooleanValue(true),        vec![Key("b"), Index(0)]),
2994                     (StringValue("foo\nbar".to_string()),  vec![Key("b"), Index(1)]),
2995                     (ObjectStart,               vec![Key("b"), Index(2)]),
2996                       (ObjectStart,             vec![Key("b"), Index(2), Key("c")]),
2997                         (NullValue,             vec![Key("b"), Index(2), Key("c"), Key("d")]),
2998                       (ObjectEnd,               vec![Key("b"), Index(2), Key("c")]),
2999                     (ObjectEnd,                 vec![Key("b"), Index(2)]),
3000                   (ListEnd,                     vec![Key("b")]),
3001                 (ObjectEnd,                     vec![]),
3002             ]
3003         );
3004     }
3005     #[test]
3006     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
3007     fn test_read_list_streaming() {
3008         assert_stream_equal(
3009             "[]",
3010             vec![
3011                 (ListStart, vec![]),
3012                 (ListEnd,   vec![]),
3013             ]
3014         );
3015         assert_stream_equal(
3016             "[ ]",
3017             vec![
3018                 (ListStart, vec![]),
3019                 (ListEnd,   vec![]),
3020             ]
3021         );
3022         assert_stream_equal(
3023             "[true]",
3024             vec![
3025                 (ListStart,              vec![]),
3026                     (BooleanValue(true), vec![Index(0)]),
3027                 (ListEnd,                vec![]),
3028             ]
3029         );
3030         assert_stream_equal(
3031             "[ false ]",
3032             vec![
3033                 (ListStart,               vec![]),
3034                     (BooleanValue(false), vec![Index(0)]),
3035                 (ListEnd,                 vec![]),
3036             ]
3037         );
3038         assert_stream_equal(
3039             "[null]",
3040             vec![
3041                 (ListStart,     vec![]),
3042                     (NullValue, vec![Index(0)]),
3043                 (ListEnd,       vec![]),
3044             ]
3045         );
3046         assert_stream_equal(
3047             "[3, 1]",
3048             vec![
3049                 (ListStart,     vec![]),
3050                     (NumberValue(3.0), vec![Index(0)]),
3051                     (NumberValue(1.0), vec![Index(1)]),
3052                 (ListEnd,       vec![]),
3053             ]
3054         );
3055         assert_stream_equal(
3056             "\n[3, 2]\n",
3057             vec![
3058                 (ListStart,     vec![]),
3059                     (NumberValue(3.0), vec![Index(0)]),
3060                     (NumberValue(2.0), vec![Index(1)]),
3061                 (ListEnd,       vec![]),
3062             ]
3063         );
3064         assert_stream_equal(
3065             "[2, [4, 1]]",
3066             vec![
3067                 (ListStart,                 vec![]),
3068                     (NumberValue(2.0),      vec![Index(0)]),
3069                     (ListStart,             vec![Index(1)]),
3070                         (NumberValue(4.0),  vec![Index(1), Index(0)]),
3071                         (NumberValue(1.0),  vec![Index(1), Index(1)]),
3072                     (ListEnd,               vec![Index(1)]),
3073                 (ListEnd,                   vec![]),
3074             ]
3075         );
3076
3077         assert_eq!(last_event("["), Error(SyntaxError(EOFWhileParsingValue, 1,  2)));
3078
3079         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
3080         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingList,  1, 3)));
3081         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
3082         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
3083         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
3084
3085     }
3086     #[test]
3087     fn test_trailing_characters_streaming() {
3088         assert_eq!(last_event("nulla"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3089         assert_eq!(last_event("truea"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3090         assert_eq!(last_event("falsea"), Error(SyntaxError(TrailingCharacters, 1, 6)));
3091         assert_eq!(last_event("1a"),     Error(SyntaxError(TrailingCharacters, 1, 2)));
3092         assert_eq!(last_event("[]a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3093         assert_eq!(last_event("{}a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3094     }
3095     #[test]
3096     fn test_read_identifiers_streaming() {
3097         assert_eq!(Parser::new("null".chars()).next(), Some(NullValue));
3098         assert_eq!(Parser::new("true".chars()).next(), Some(BooleanValue(true)));
3099         assert_eq!(Parser::new("false".chars()).next(), Some(BooleanValue(false)));
3100
3101         assert_eq!(last_event("n"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3102         assert_eq!(last_event("nul"),  Error(SyntaxError(InvalidSyntax, 1, 4)));
3103         assert_eq!(last_event("t"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3104         assert_eq!(last_event("truz"), Error(SyntaxError(InvalidSyntax, 1, 4)));
3105         assert_eq!(last_event("f"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3106         assert_eq!(last_event("faz"),  Error(SyntaxError(InvalidSyntax, 1, 3)));
3107     }
3108
3109     #[test]
3110     fn test_stack() {
3111         let mut stack = Stack::new();
3112
3113         assert!(stack.is_empty());
3114         assert!(stack.len() == 0);
3115         assert!(!stack.last_is_index());
3116
3117         stack.push_index(0);
3118         stack.bump_index();
3119
3120         assert!(stack.len() == 1);
3121         assert!(stack.is_equal_to([Index(1)]));
3122         assert!(stack.starts_with([Index(1)]));
3123         assert!(stack.ends_with([Index(1)]));
3124         assert!(stack.last_is_index());
3125         assert!(stack.get(0) == Index(1));
3126
3127         stack.push_key("foo".to_string());
3128
3129         assert!(stack.len() == 2);
3130         assert!(stack.is_equal_to([Index(1), Key("foo")]));
3131         assert!(stack.starts_with([Index(1), Key("foo")]));
3132         assert!(stack.starts_with([Index(1)]));
3133         assert!(stack.ends_with([Index(1), Key("foo")]));
3134         assert!(stack.ends_with([Key("foo")]));
3135         assert!(!stack.last_is_index());
3136         assert!(stack.get(0) == Index(1));
3137         assert!(stack.get(1) == Key("foo"));
3138
3139         stack.push_key("bar".to_string());
3140
3141         assert!(stack.len() == 3);
3142         assert!(stack.is_equal_to([Index(1), Key("foo"), Key("bar")]));
3143         assert!(stack.starts_with([Index(1)]));
3144         assert!(stack.starts_with([Index(1), Key("foo")]));
3145         assert!(stack.starts_with([Index(1), Key("foo"), Key("bar")]));
3146         assert!(stack.ends_with([Key("bar")]));
3147         assert!(stack.ends_with([Key("foo"), Key("bar")]));
3148         assert!(stack.ends_with([Index(1), Key("foo"), Key("bar")]));
3149         assert!(!stack.last_is_index());
3150         assert!(stack.get(0) == Index(1));
3151         assert!(stack.get(1) == Key("foo"));
3152         assert!(stack.get(2) == Key("bar"));
3153
3154         stack.pop();
3155
3156         assert!(stack.len() == 2);
3157         assert!(stack.is_equal_to([Index(1), Key("foo")]));
3158         assert!(stack.starts_with([Index(1), Key("foo")]));
3159         assert!(stack.starts_with([Index(1)]));
3160         assert!(stack.ends_with([Index(1), Key("foo")]));
3161         assert!(stack.ends_with([Key("foo")]));
3162         assert!(!stack.last_is_index());
3163         assert!(stack.get(0) == Index(1));
3164         assert!(stack.get(1) == Key("foo"));
3165     }
3166
3167     #[test]
3168     fn test_to_json() {
3169         use std::collections::{HashMap,TreeMap};
3170         use super::ToJson;
3171
3172         let list2 = List(vec!(Number(1.0_f64), Number(2.0_f64)));
3173         let list3 = List(vec!(Number(1.0f64), Number(2.0f64), Number(3.0f64)));
3174         let object = {
3175             let mut tree_map = TreeMap::new();
3176             tree_map.insert("a".to_string(), Number(1.0_f64));
3177             tree_map.insert("b".to_string(), Number(2.0_f64));
3178             Object(tree_map)
3179         };
3180
3181         assert_eq!(list2.to_json(), list2);
3182         assert_eq!(object.to_json(), object);
3183         assert_eq!(3_i.to_json(), Number(3.0_f64));
3184         assert_eq!(4_i8.to_json(), Number(4.0_f64));
3185         assert_eq!(5_i16.to_json(), Number(5.0_f64));
3186         assert_eq!(6_i32.to_json(), Number(6.0_f64));
3187         assert_eq!(7_i64.to_json(), Number(7.0_f64));
3188         assert_eq!(8_u.to_json(), Number(8.0_f64));
3189         assert_eq!(9_u8.to_json(), Number(9.0_f64));
3190         assert_eq!(10_u16.to_json(), Number(10.0_f64));
3191         assert_eq!(11_u32.to_json(), Number(11.0_f64));
3192         assert_eq!(12_u64.to_json(), Number(12.0_f64));
3193         assert_eq!(13.0_f32.to_json(), Number(13.0_f64));
3194         assert_eq!(14.0_f64.to_json(), Number(14.0_f64));
3195         assert_eq!(().to_json(), Null);
3196         assert_eq!(f32::INFINITY.to_json(), Null);
3197         assert_eq!(f64::NAN.to_json(), Null);
3198         assert_eq!(true.to_json(), Boolean(true));
3199         assert_eq!(false.to_json(), Boolean(false));
3200         assert_eq!("abc".to_string().to_json(), String("abc".to_string()));
3201         assert_eq!((1i, 2i).to_json(), list2);
3202         assert_eq!((1i, 2i, 3i).to_json(), list3);
3203         assert_eq!([1i, 2].to_json(), list2);
3204         assert_eq!((&[1i, 2, 3]).to_json(), list3);
3205         assert_eq!((vec![1i, 2]).to_json(), list2);
3206         assert_eq!(vec!(1i, 2i, 3i).to_json(), list3);
3207         let mut tree_map = TreeMap::new();
3208         tree_map.insert("a".to_string(), 1i);
3209         tree_map.insert("b".to_string(), 2);
3210         assert_eq!(tree_map.to_json(), object);
3211         let mut hash_map = HashMap::new();
3212         hash_map.insert("a".to_string(), 1i);
3213         hash_map.insert("b".to_string(), 2);
3214         assert_eq!(hash_map.to_json(), object);
3215         assert_eq!(Some(15i).to_json(), Number(15f64));
3216         assert_eq!(None::<int>.to_json(), Null);
3217     }
3218
3219     #[bench]
3220     fn bench_streaming_small(b: &mut Bencher) {
3221         b.iter( || {
3222             let mut parser = Parser::new(
3223                 r#"{
3224                     "a": 1.0,
3225                     "b": [
3226                         true,
3227                         "foo\nbar",
3228                         { "c": {"d": null} }
3229                     ]
3230                 }"#.chars()
3231             );
3232             loop {
3233                 match parser.next() {
3234                     None => return,
3235                     _ => {}
3236                 }
3237             }
3238         });
3239     }
3240     #[bench]
3241     fn bench_small(b: &mut Bencher) {
3242         b.iter( || {
3243             let _ = from_str(r#"{
3244                 "a": 1.0,
3245                 "b": [
3246                     true,
3247                     "foo\nbar",
3248                     { "c": {"d": null} }
3249                 ]
3250             }"#);
3251         });
3252     }
3253
3254     fn big_json() -> String {
3255         let mut src = "[\n".to_string();
3256         for _ in range(0i, 500) {
3257             src.push_str(r#"{ "a": true, "b": null, "c":3.1415, "d": "Hello world", "e": \
3258                             [1,2,3]},"#);
3259         }
3260         src.push_str("{}]");
3261         return src;
3262     }
3263
3264     #[bench]
3265     fn bench_streaming_large(b: &mut Bencher) {
3266         let src = big_json();
3267         b.iter( || {
3268             let mut parser = Parser::new(src.as_slice().chars());
3269             loop {
3270                 match parser.next() {
3271                     None => return,
3272                     _ => {}
3273                 }
3274             }
3275         });
3276     }
3277     #[bench]
3278     fn bench_large(b: &mut Bencher) {
3279         let src = big_json();
3280         b.iter( || { let _ = from_str(src.as_slice()); });
3281     }
3282 }