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