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