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             match target.find(*key) {
1056                 Some(t) => { target = t; },
1057                 None => return None
1058             }
1059         }
1060         Some(target)
1061     }
1062
1063     /// If the Json value is an Object, performs a depth-first search until
1064     /// a value associated with the provided key is found. If no value is found
1065     /// or the Json value is not an Object, returns None.
1066     pub fn search<'a>(&'a self, key: &str) -> Option<&'a Json> {
1067         match self {
1068             &Json::Object(ref map) => {
1069                 match map.get(key) {
1070                     Some(json_value) => Some(json_value),
1071                     None => {
1072                         for (_, v) in map {
1073                             match v.search(key) {
1074                                 x if x.is_some() => return x,
1075                                 _ => ()
1076                             }
1077                         }
1078                         None
1079                     }
1080                 }
1081             },
1082             _ => None
1083         }
1084     }
1085
1086     /// Returns true if the Json value is an Object. Returns false otherwise.
1087     pub fn is_object(&self) -> bool {
1088         self.as_object().is_some()
1089     }
1090
1091     /// If the Json value is an Object, returns the associated BTreeMap.
1092     /// Returns None otherwise.
1093     pub fn as_object(&self) -> Option<&Object> {
1094         match *self {
1095             Json::Object(ref map) => Some(map),
1096             _ => None
1097         }
1098     }
1099
1100     /// Returns true if the Json value is an Array. Returns false otherwise.
1101     pub fn is_array(&self) -> bool {
1102         self.as_array().is_some()
1103     }
1104
1105     /// If the Json value is an Array, returns the associated vector.
1106     /// Returns None otherwise.
1107     pub fn as_array(&self) -> Option<&Array> {
1108         match *self {
1109             Json::Array(ref array) => Some(&*array),
1110             _ => None
1111         }
1112     }
1113
1114     /// Returns true if the Json value is a String. Returns false otherwise.
1115     pub fn is_string(&self) -> bool {
1116         self.as_string().is_some()
1117     }
1118
1119     /// If the Json value is a String, returns the associated str.
1120     /// Returns None otherwise.
1121     pub fn as_string(&self) -> Option<&str> {
1122         match *self {
1123             Json::String(ref s) => Some(&s[..]),
1124             _ => None
1125         }
1126     }
1127
1128     /// Returns true if the Json value is a Number. Returns false otherwise.
1129     pub fn is_number(&self) -> bool {
1130         match *self {
1131             Json::I64(_) | Json::U64(_) | Json::F64(_) => true,
1132             _ => false,
1133         }
1134     }
1135
1136     /// Returns true if the Json value is a i64. Returns false otherwise.
1137     pub fn is_i64(&self) -> bool {
1138         match *self {
1139             Json::I64(_) => true,
1140             _ => false,
1141         }
1142     }
1143
1144     /// Returns true if the Json value is a u64. Returns false otherwise.
1145     pub fn is_u64(&self) -> bool {
1146         match *self {
1147             Json::U64(_) => true,
1148             _ => false,
1149         }
1150     }
1151
1152     /// Returns true if the Json value is a f64. Returns false otherwise.
1153     pub fn is_f64(&self) -> bool {
1154         match *self {
1155             Json::F64(_) => true,
1156             _ => false,
1157         }
1158     }
1159
1160     /// If the Json value is a number, return or cast it to a i64.
1161     /// Returns None otherwise.
1162     pub fn as_i64(&self) -> Option<i64> {
1163         match *self {
1164             Json::I64(n) => Some(n),
1165             Json::U64(n) => Some(n as i64),
1166             _ => None
1167         }
1168     }
1169
1170     /// If the Json value is a number, return or cast it to a u64.
1171     /// Returns None otherwise.
1172     pub fn as_u64(&self) -> Option<u64> {
1173         match *self {
1174             Json::I64(n) => Some(n as u64),
1175             Json::U64(n) => Some(n),
1176             _ => None
1177         }
1178     }
1179
1180     /// If the Json value is a number, return or cast it to a f64.
1181     /// Returns None otherwise.
1182     pub fn as_f64(&self) -> Option<f64> {
1183         match *self {
1184             Json::I64(n) => Some(n as f64),
1185             Json::U64(n) => Some(n as f64),
1186             Json::F64(n) => Some(n),
1187             _ => None
1188         }
1189     }
1190
1191     /// Returns true if the Json value is a Boolean. Returns false otherwise.
1192     pub fn is_boolean(&self) -> bool {
1193         self.as_boolean().is_some()
1194     }
1195
1196     /// If the Json value is a Boolean, returns the associated bool.
1197     /// Returns None otherwise.
1198     pub fn as_boolean(&self) -> Option<bool> {
1199         match *self {
1200             Json::Boolean(b) => Some(b),
1201             _ => None
1202         }
1203     }
1204
1205     /// Returns true if the Json value is a Null. Returns false otherwise.
1206     pub fn is_null(&self) -> bool {
1207         self.as_null().is_some()
1208     }
1209
1210     /// If the Json value is a Null, returns ().
1211     /// Returns None otherwise.
1212     pub fn as_null(&self) -> Option<()> {
1213         match *self {
1214             Json::Null => Some(()),
1215             _ => None
1216         }
1217     }
1218 }
1219
1220 impl<'a> Index<&'a str>  for Json {
1221     type Output = Json;
1222
1223     fn index(&self, idx: &'a str) -> &Json {
1224         self.find(idx).unwrap()
1225     }
1226 }
1227
1228 impl Index<usize> for Json {
1229     type Output = Json;
1230
1231     fn index(&self, idx: usize) -> &Json {
1232         match *self {
1233             Json::Array(ref v) => &v[idx],
1234             _ => panic!("can only index Json with usize if it is an array")
1235         }
1236     }
1237 }
1238
1239 /// The output of the streaming parser.
1240 #[derive(PartialEq, Clone, Debug)]
1241 pub enum JsonEvent {
1242     ObjectStart,
1243     ObjectEnd,
1244     ArrayStart,
1245     ArrayEnd,
1246     BooleanValue(bool),
1247     I64Value(i64),
1248     U64Value(u64),
1249     F64Value(f64),
1250     StringValue(string::String),
1251     NullValue,
1252     Error(ParserError),
1253 }
1254
1255 #[derive(PartialEq, Debug)]
1256 enum ParserState {
1257     // Parse a value in an array, true means first element.
1258     ParseArray(bool),
1259     // Parse ',' or ']' after an element in an array.
1260     ParseArrayComma,
1261     // Parse a key:value in an object, true means first element.
1262     ParseObject(bool),
1263     // Parse ',' or ']' after an element in an object.
1264     ParseObjectComma,
1265     // Initial state.
1266     ParseStart,
1267     // Expecting the stream to end.
1268     ParseBeforeFinish,
1269     // Parsing can't continue.
1270     ParseFinished,
1271 }
1272
1273 /// A Stack represents the current position of the parser in the logical
1274 /// structure of the JSON stream.
1275 /// For example foo.bar[3].x
1276 pub struct Stack {
1277     stack: Vec<InternalStackElement>,
1278     str_buffer: Vec<u8>,
1279 }
1280
1281 /// StackElements compose a Stack.
1282 /// For example, StackElement::Key("foo"), StackElement::Key("bar"),
1283 /// StackElement::Index(3) and StackElement::Key("x") are the
1284 /// StackElements compositing the stack that represents foo.bar[3].x
1285 #[derive(PartialEq, Clone, Debug)]
1286 pub enum StackElement<'l> {
1287     Index(u32),
1288     Key(&'l str),
1289 }
1290
1291 // Internally, Key elements are stored as indices in a buffer to avoid
1292 // allocating a string for every member of an object.
1293 #[derive(PartialEq, Clone, Debug)]
1294 enum InternalStackElement {
1295     InternalIndex(u32),
1296     InternalKey(u16, u16), // start, size
1297 }
1298
1299 impl Stack {
1300     pub fn new() -> Stack {
1301         Stack { stack: Vec::new(), str_buffer: Vec::new() }
1302     }
1303
1304     /// Returns The number of elements in the Stack.
1305     pub fn len(&self) -> usize { self.stack.len() }
1306
1307     /// Returns true if the stack is empty.
1308     pub fn is_empty(&self) -> bool { self.stack.is_empty() }
1309
1310     /// Provides access to the StackElement at a given index.
1311     /// lower indices are at the bottom of the stack while higher indices are
1312     /// at the top.
1313     pub fn get(&self, idx: usize) -> StackElement {
1314         match self.stack[idx] {
1315             InternalIndex(i) => StackElement::Index(i),
1316             InternalKey(start, size) => {
1317                 StackElement::Key(str::from_utf8(
1318                     &self.str_buffer[start as usize .. start as usize + size as usize])
1319                         .unwrap())
1320             }
1321         }
1322     }
1323
1324     /// Compares this stack with an array of StackElements.
1325     pub fn is_equal_to(&self, rhs: &[StackElement]) -> bool {
1326         if self.stack.len() != rhs.len() { return false; }
1327         for (i, r) in rhs.iter().enumerate() {
1328             if self.get(i) != *r { return false; }
1329         }
1330         true
1331     }
1332
1333     /// Returns true if the bottom-most elements of this stack are the same as
1334     /// the ones passed as parameter.
1335     pub fn starts_with(&self, rhs: &[StackElement]) -> bool {
1336         if self.stack.len() < rhs.len() { return false; }
1337         for (i, r) in rhs.iter().enumerate() {
1338             if self.get(i) != *r { return false; }
1339         }
1340         true
1341     }
1342
1343     /// Returns true if the top-most elements of this stack are the same as
1344     /// the ones passed as parameter.
1345     pub fn ends_with(&self, rhs: &[StackElement]) -> bool {
1346         if self.stack.len() < rhs.len() { return false; }
1347         let offset = self.stack.len() - rhs.len();
1348         for (i, r) in rhs.iter().enumerate() {
1349             if self.get(i + offset) != *r { return false; }
1350         }
1351         true
1352     }
1353
1354     /// Returns the top-most element (if any).
1355     pub fn top(&self) -> Option<StackElement> {
1356         match self.stack.last() {
1357             None => None,
1358             Some(&InternalIndex(i)) => Some(StackElement::Index(i)),
1359             Some(&InternalKey(start, size)) => {
1360                 Some(StackElement::Key(str::from_utf8(
1361                     &self.str_buffer[start as usize .. (start+size) as usize]
1362                 ).unwrap()))
1363             }
1364         }
1365     }
1366
1367     // Used by Parser to insert StackElement::Key elements at the top of the stack.
1368     fn push_key(&mut self, key: string::String) {
1369         self.stack.push(InternalKey(self.str_buffer.len() as u16, key.len() as u16));
1370         for c in key.as_bytes() {
1371             self.str_buffer.push(*c);
1372         }
1373     }
1374
1375     // Used by Parser to insert StackElement::Index elements at the top of the stack.
1376     fn push_index(&mut self, index: u32) {
1377         self.stack.push(InternalIndex(index));
1378     }
1379
1380     // Used by Parser to remove the top-most element of the stack.
1381     fn pop(&mut self) {
1382         assert!(!self.is_empty());
1383         match *self.stack.last().unwrap() {
1384             InternalKey(_, sz) => {
1385                 let new_size = self.str_buffer.len() - sz as usize;
1386                 self.str_buffer.truncate(new_size);
1387             }
1388             InternalIndex(_) => {}
1389         }
1390         self.stack.pop();
1391     }
1392
1393     // Used by Parser to test whether the top-most element is an index.
1394     fn last_is_index(&self) -> bool {
1395         if self.is_empty() { return false; }
1396         return match *self.stack.last().unwrap() {
1397             InternalIndex(_) => true,
1398             _ => false,
1399         }
1400     }
1401
1402     // Used by Parser to increment the index of the top-most element.
1403     fn bump_index(&mut self) {
1404         let len = self.stack.len();
1405         let idx = match *self.stack.last().unwrap() {
1406             InternalIndex(i) => { i + 1 }
1407             _ => { panic!(); }
1408         };
1409         self.stack[len - 1] = InternalIndex(idx);
1410     }
1411 }
1412
1413 /// A streaming JSON parser implemented as an iterator of JsonEvent, consuming
1414 /// an iterator of char.
1415 pub struct Parser<T> {
1416     rdr: T,
1417     ch: Option<char>,
1418     line: usize,
1419     col: usize,
1420     // We maintain a stack representing where we are in the logical structure
1421     // of the JSON stream.
1422     stack: Stack,
1423     // A state machine is kept to make it possible to interrupt and resume parsing.
1424     state: ParserState,
1425 }
1426
1427 impl<T: Iterator<Item=char>> Iterator for Parser<T> {
1428     type Item = JsonEvent;
1429
1430     fn next(&mut self) -> Option<JsonEvent> {
1431         if self.state == ParseFinished {
1432             return None;
1433         }
1434
1435         if self.state == ParseBeforeFinish {
1436             self.parse_whitespace();
1437             // Make sure there is no trailing characters.
1438             if self.eof() {
1439                 self.state = ParseFinished;
1440                 return None;
1441             } else {
1442                 return Some(self.error_event(TrailingCharacters));
1443             }
1444         }
1445
1446         Some(self.parse())
1447     }
1448 }
1449
1450 impl<T: Iterator<Item=char>> Parser<T> {
1451     /// Creates the JSON parser.
1452     pub fn new(rdr: T) -> Parser<T> {
1453         let mut p = Parser {
1454             rdr,
1455             ch: Some('\x00'),
1456             line: 1,
1457             col: 0,
1458             stack: Stack::new(),
1459             state: ParseStart,
1460         };
1461         p.bump();
1462         p
1463     }
1464
1465     /// Provides access to the current position in the logical structure of the
1466     /// JSON stream.
1467     pub fn stack(&self) -> &Stack {
1468         &self.stack
1469     }
1470
1471     fn eof(&self) -> bool { self.ch.is_none() }
1472     fn ch_or_null(&self) -> char { self.ch.unwrap_or('\x00') }
1473     fn bump(&mut self) {
1474         self.ch = self.rdr.next();
1475
1476         if self.ch_is('\n') {
1477             self.line += 1;
1478             self.col = 1;
1479         } else {
1480             self.col += 1;
1481         }
1482     }
1483
1484     fn next_char(&mut self) -> Option<char> {
1485         self.bump();
1486         self.ch
1487     }
1488     fn ch_is(&self, c: char) -> bool {
1489         self.ch == Some(c)
1490     }
1491
1492     fn error<U>(&self, reason: ErrorCode) -> Result<U, ParserError> {
1493         Err(SyntaxError(reason, self.line, self.col))
1494     }
1495
1496     fn parse_whitespace(&mut self) {
1497         while self.ch_is(' ') ||
1498               self.ch_is('\n') ||
1499               self.ch_is('\t') ||
1500               self.ch_is('\r') { self.bump(); }
1501     }
1502
1503     fn parse_number(&mut self) -> JsonEvent {
1504         let mut neg = false;
1505
1506         if self.ch_is('-') {
1507             self.bump();
1508             neg = true;
1509         }
1510
1511         let res = match self.parse_u64() {
1512             Ok(res) => res,
1513             Err(e) => { return Error(e); }
1514         };
1515
1516         if self.ch_is('.') || self.ch_is('e') || self.ch_is('E') {
1517             let mut res = res as f64;
1518
1519             if self.ch_is('.') {
1520                 res = match self.parse_decimal(res) {
1521                     Ok(res) => res,
1522                     Err(e) => { return Error(e); }
1523                 };
1524             }
1525
1526             if self.ch_is('e') || self.ch_is('E') {
1527                 res = match self.parse_exponent(res) {
1528                     Ok(res) => res,
1529                     Err(e) => { return Error(e); }
1530                 };
1531             }
1532
1533             if neg {
1534                 res *= -1.0;
1535             }
1536
1537             F64Value(res)
1538         } else {
1539             if neg {
1540                 let res = (res as i64).wrapping_neg();
1541
1542                 // Make sure we didn't underflow.
1543                 if res > 0 {
1544                     Error(SyntaxError(InvalidNumber, self.line, self.col))
1545                 } else {
1546                     I64Value(res)
1547                 }
1548             } else {
1549                 U64Value(res)
1550             }
1551         }
1552     }
1553
1554     fn parse_u64(&mut self) -> Result<u64, ParserError> {
1555         let mut accum = 0u64;
1556         let last_accum = 0; // necessary to detect overflow.
1557
1558         match self.ch_or_null() {
1559             '0' => {
1560                 self.bump();
1561
1562                 // A leading '0' must be the only digit before the decimal point.
1563                 if let '0' ... '9' = self.ch_or_null() {
1564                     return self.error(InvalidNumber)
1565                 }
1566             },
1567             '1' ... '9' => {
1568                 while !self.eof() {
1569                     match self.ch_or_null() {
1570                         c @ '0' ... '9' => {
1571                             accum = accum.wrapping_mul(10);
1572                             accum = accum.wrapping_add((c as u64) - ('0' as u64));
1573
1574                             // Detect overflow by comparing to the last value.
1575                             if accum <= last_accum { return self.error(InvalidNumber); }
1576
1577                             self.bump();
1578                         }
1579                         _ => break,
1580                     }
1581                 }
1582             }
1583             _ => return self.error(InvalidNumber),
1584         }
1585
1586         Ok(accum)
1587     }
1588
1589     fn parse_decimal(&mut self, mut res: f64) -> Result<f64, ParserError> {
1590         self.bump();
1591
1592         // Make sure a digit follows the decimal place.
1593         match self.ch_or_null() {
1594             '0' ... '9' => (),
1595              _ => return self.error(InvalidNumber)
1596         }
1597
1598         let mut dec = 1.0;
1599         while !self.eof() {
1600             match self.ch_or_null() {
1601                 c @ '0' ... '9' => {
1602                     dec /= 10.0;
1603                     res += (((c as isize) - ('0' as isize)) as f64) * dec;
1604                     self.bump();
1605                 }
1606                 _ => break,
1607             }
1608         }
1609
1610         Ok(res)
1611     }
1612
1613     fn parse_exponent(&mut self, mut res: f64) -> Result<f64, ParserError> {
1614         self.bump();
1615
1616         let mut exp = 0;
1617         let mut neg_exp = false;
1618
1619         if self.ch_is('+') {
1620             self.bump();
1621         } else if self.ch_is('-') {
1622             self.bump();
1623             neg_exp = true;
1624         }
1625
1626         // Make sure a digit follows the exponent place.
1627         match self.ch_or_null() {
1628             '0' ... '9' => (),
1629             _ => return self.error(InvalidNumber)
1630         }
1631         while !self.eof() {
1632             match self.ch_or_null() {
1633                 c @ '0' ... '9' => {
1634                     exp *= 10;
1635                     exp += (c as usize) - ('0' as usize);
1636
1637                     self.bump();
1638                 }
1639                 _ => break
1640             }
1641         }
1642
1643         let exp = 10_f64.powi(exp as i32);
1644         if neg_exp {
1645             res /= exp;
1646         } else {
1647             res *= exp;
1648         }
1649
1650         Ok(res)
1651     }
1652
1653     fn decode_hex_escape(&mut self) -> Result<u16, ParserError> {
1654         let mut i = 0;
1655         let mut n = 0;
1656         while i < 4 && !self.eof() {
1657             self.bump();
1658             n = match self.ch_or_null() {
1659                 c @ '0' ... '9' => n * 16 + ((c as u16) - ('0' as u16)),
1660                 'a' | 'A' => n * 16 + 10,
1661                 'b' | 'B' => n * 16 + 11,
1662                 'c' | 'C' => n * 16 + 12,
1663                 'd' | 'D' => n * 16 + 13,
1664                 'e' | 'E' => n * 16 + 14,
1665                 'f' | 'F' => n * 16 + 15,
1666                 _ => return self.error(InvalidEscape)
1667             };
1668
1669             i += 1;
1670         }
1671
1672         // Error out if we didn't parse 4 digits.
1673         if i != 4 {
1674             return self.error(InvalidEscape);
1675         }
1676
1677         Ok(n)
1678     }
1679
1680     fn parse_str(&mut self) -> Result<string::String, ParserError> {
1681         let mut escape = false;
1682         let mut res = string::String::new();
1683
1684         loop {
1685             self.bump();
1686             if self.eof() {
1687                 return self.error(EOFWhileParsingString);
1688             }
1689
1690             if escape {
1691                 match self.ch_or_null() {
1692                     '"' => res.push('"'),
1693                     '\\' => res.push('\\'),
1694                     '/' => res.push('/'),
1695                     'b' => res.push('\x08'),
1696                     'f' => res.push('\x0c'),
1697                     'n' => res.push('\n'),
1698                     'r' => res.push('\r'),
1699                     't' => res.push('\t'),
1700                     'u' => match self.decode_hex_escape()? {
1701                         0xDC00 ... 0xDFFF => {
1702                             return self.error(LoneLeadingSurrogateInHexEscape)
1703                         }
1704
1705                         // Non-BMP characters are encoded as a sequence of
1706                         // two hex escapes, representing UTF-16 surrogates.
1707                         n1 @ 0xD800 ... 0xDBFF => {
1708                             match (self.next_char(), self.next_char()) {
1709                                 (Some('\\'), Some('u')) => (),
1710                                 _ => return self.error(UnexpectedEndOfHexEscape),
1711                             }
1712
1713                             let n2 = self.decode_hex_escape()?;
1714                             if n2 < 0xDC00 || n2 > 0xDFFF {
1715                                 return self.error(LoneLeadingSurrogateInHexEscape)
1716                             }
1717                             let c = (((n1 - 0xD800) as u32) << 10 |
1718                                      (n2 - 0xDC00) as u32) + 0x1_0000;
1719                             res.push(char::from_u32(c).unwrap());
1720                         }
1721
1722                         n => match char::from_u32(n as u32) {
1723                             Some(c) => res.push(c),
1724                             None => return self.error(InvalidUnicodeCodePoint),
1725                         },
1726                     },
1727                     _ => return self.error(InvalidEscape),
1728                 }
1729                 escape = false;
1730             } else if self.ch_is('\\') {
1731                 escape = true;
1732             } else {
1733                 match self.ch {
1734                     Some('"') => {
1735                         self.bump();
1736                         return Ok(res);
1737                     },
1738                     Some(c) => res.push(c),
1739                     None => unreachable!()
1740                 }
1741             }
1742         }
1743     }
1744
1745     // Invoked at each iteration, consumes the stream until it has enough
1746     // information to return a JsonEvent.
1747     // Manages an internal state so that parsing can be interrupted and resumed.
1748     // Also keeps track of the position in the logical structure of the json
1749     // stream isize the form of a stack that can be queried by the user using the
1750     // stack() method.
1751     fn parse(&mut self) -> JsonEvent {
1752         loop {
1753             // The only paths where the loop can spin a new iteration
1754             // are in the cases ParseArrayComma and ParseObjectComma if ','
1755             // is parsed. In these cases the state is set to (respectively)
1756             // ParseArray(false) and ParseObject(false), which always return,
1757             // so there is no risk of getting stuck in an infinite loop.
1758             // All other paths return before the end of the loop's iteration.
1759             self.parse_whitespace();
1760
1761             match self.state {
1762                 ParseStart => {
1763                     return self.parse_start();
1764                 }
1765                 ParseArray(first) => {
1766                     return self.parse_array(first);
1767                 }
1768                 ParseArrayComma => {
1769                     if let Some(evt) = self.parse_array_comma_or_end() {
1770                         return evt;
1771                     }
1772                 }
1773                 ParseObject(first) => {
1774                     return self.parse_object(first);
1775                 }
1776                 ParseObjectComma => {
1777                     self.stack.pop();
1778                     if self.ch_is(',') {
1779                         self.state = ParseObject(false);
1780                         self.bump();
1781                     } else {
1782                         return self.parse_object_end();
1783                     }
1784                 }
1785                 _ => {
1786                     return self.error_event(InvalidSyntax);
1787                 }
1788             }
1789         }
1790     }
1791
1792     fn parse_start(&mut self) -> JsonEvent {
1793         let val = self.parse_value();
1794         self.state = match val {
1795             Error(_) => ParseFinished,
1796             ArrayStart => ParseArray(true),
1797             ObjectStart => ParseObject(true),
1798             _ => ParseBeforeFinish,
1799         };
1800         val
1801     }
1802
1803     fn parse_array(&mut self, first: bool) -> JsonEvent {
1804         if self.ch_is(']') {
1805             if !first {
1806                 self.error_event(InvalidSyntax)
1807             } else {
1808                 self.state = if self.stack.is_empty() {
1809                     ParseBeforeFinish
1810                 } else if self.stack.last_is_index() {
1811                     ParseArrayComma
1812                 } else {
1813                     ParseObjectComma
1814                 };
1815                 self.bump();
1816                 ArrayEnd
1817             }
1818         } else {
1819             if first {
1820                 self.stack.push_index(0);
1821             }
1822             let val = self.parse_value();
1823             self.state = match val {
1824                 Error(_) => ParseFinished,
1825                 ArrayStart => ParseArray(true),
1826                 ObjectStart => ParseObject(true),
1827                 _ => ParseArrayComma,
1828             };
1829             val
1830         }
1831     }
1832
1833     fn parse_array_comma_or_end(&mut self) -> Option<JsonEvent> {
1834         if self.ch_is(',') {
1835             self.stack.bump_index();
1836             self.state = ParseArray(false);
1837             self.bump();
1838             None
1839         } else if self.ch_is(']') {
1840             self.stack.pop();
1841             self.state = if self.stack.is_empty() {
1842                 ParseBeforeFinish
1843             } else if self.stack.last_is_index() {
1844                 ParseArrayComma
1845             } else {
1846                 ParseObjectComma
1847             };
1848             self.bump();
1849             Some(ArrayEnd)
1850         } else if self.eof() {
1851             Some(self.error_event(EOFWhileParsingArray))
1852         } else {
1853             Some(self.error_event(InvalidSyntax))
1854         }
1855     }
1856
1857     fn parse_object(&mut self, first: bool) -> JsonEvent {
1858         if self.ch_is('}') {
1859             if !first {
1860                 if self.stack.is_empty() {
1861                     return self.error_event(TrailingComma);
1862                 } else {
1863                     self.stack.pop();
1864                 }
1865             }
1866             self.state = if self.stack.is_empty() {
1867                 ParseBeforeFinish
1868             } else if self.stack.last_is_index() {
1869                 ParseArrayComma
1870             } else {
1871                 ParseObjectComma
1872             };
1873             self.bump();
1874             return ObjectEnd;
1875         }
1876         if self.eof() {
1877             return self.error_event(EOFWhileParsingObject);
1878         }
1879         if !self.ch_is('"') {
1880             return self.error_event(KeyMustBeAString);
1881         }
1882         let s = match self.parse_str() {
1883             Ok(s) => s,
1884             Err(e) => {
1885                 self.state = ParseFinished;
1886                 return Error(e);
1887             }
1888         };
1889         self.parse_whitespace();
1890         if self.eof() {
1891             return self.error_event(EOFWhileParsingObject);
1892         } else if self.ch_or_null() != ':' {
1893             return self.error_event(ExpectedColon);
1894         }
1895         self.stack.push_key(s);
1896         self.bump();
1897         self.parse_whitespace();
1898
1899         let val = self.parse_value();
1900
1901         self.state = match val {
1902             Error(_) => ParseFinished,
1903             ArrayStart => ParseArray(true),
1904             ObjectStart => ParseObject(true),
1905             _ => ParseObjectComma,
1906         };
1907         val
1908     }
1909
1910     fn parse_object_end(&mut self) -> JsonEvent {
1911         if self.ch_is('}') {
1912             self.state = if self.stack.is_empty() {
1913                 ParseBeforeFinish
1914             } else if self.stack.last_is_index() {
1915                 ParseArrayComma
1916             } else {
1917                 ParseObjectComma
1918             };
1919             self.bump();
1920             ObjectEnd
1921         } else if self.eof() {
1922             self.error_event(EOFWhileParsingObject)
1923         } else {
1924             self.error_event(InvalidSyntax)
1925         }
1926     }
1927
1928     fn parse_value(&mut self) -> JsonEvent {
1929         if self.eof() { return self.error_event(EOFWhileParsingValue); }
1930         match self.ch_or_null() {
1931             'n' => { self.parse_ident("ull", NullValue) }
1932             't' => { self.parse_ident("rue", BooleanValue(true)) }
1933             'f' => { self.parse_ident("alse", BooleanValue(false)) }
1934             '0' ... '9' | '-' => self.parse_number(),
1935             '"' => match self.parse_str() {
1936                 Ok(s) => StringValue(s),
1937                 Err(e) => Error(e),
1938             },
1939             '[' => {
1940                 self.bump();
1941                 ArrayStart
1942             }
1943             '{' => {
1944                 self.bump();
1945                 ObjectStart
1946             }
1947             _ => { self.error_event(InvalidSyntax) }
1948         }
1949     }
1950
1951     fn parse_ident(&mut self, ident: &str, value: JsonEvent) -> JsonEvent {
1952         if ident.chars().all(|c| Some(c) == self.next_char()) {
1953             self.bump();
1954             value
1955         } else {
1956             Error(SyntaxError(InvalidSyntax, self.line, self.col))
1957         }
1958     }
1959
1960     fn error_event(&mut self, reason: ErrorCode) -> JsonEvent {
1961         self.state = ParseFinished;
1962         Error(SyntaxError(reason, self.line, self.col))
1963     }
1964 }
1965
1966 /// A Builder consumes a json::Parser to create a generic Json structure.
1967 pub struct Builder<T> {
1968     parser: Parser<T>,
1969     token: Option<JsonEvent>,
1970 }
1971
1972 impl<T: Iterator<Item=char>> Builder<T> {
1973     /// Create a JSON Builder.
1974     pub fn new(src: T) -> Builder<T> {
1975         Builder { parser: Parser::new(src), token: None, }
1976     }
1977
1978     // Decode a Json value from a Parser.
1979     pub fn build(&mut self) -> Result<Json, BuilderError> {
1980         self.bump();
1981         let result = self.build_value();
1982         self.bump();
1983         match self.token {
1984             None => {}
1985             Some(Error(ref e)) => { return Err(e.clone()); }
1986             ref tok => { panic!("unexpected token {:?}", tok.clone()); }
1987         }
1988         result
1989     }
1990
1991     fn bump(&mut self) {
1992         self.token = self.parser.next();
1993     }
1994
1995     fn build_value(&mut self) -> Result<Json, BuilderError> {
1996         match self.token {
1997             Some(NullValue) => Ok(Json::Null),
1998             Some(I64Value(n)) => Ok(Json::I64(n)),
1999             Some(U64Value(n)) => Ok(Json::U64(n)),
2000             Some(F64Value(n)) => Ok(Json::F64(n)),
2001             Some(BooleanValue(b)) => Ok(Json::Boolean(b)),
2002             Some(StringValue(ref mut s)) => {
2003                 let mut temp = string::String::new();
2004                 swap(s, &mut temp);
2005                 Ok(Json::String(temp))
2006             }
2007             Some(Error(ref e)) => Err(e.clone()),
2008             Some(ArrayStart) => self.build_array(),
2009             Some(ObjectStart) => self.build_object(),
2010             Some(ObjectEnd) => self.parser.error(InvalidSyntax),
2011             Some(ArrayEnd) => self.parser.error(InvalidSyntax),
2012             None => self.parser.error(EOFWhileParsingValue),
2013         }
2014     }
2015
2016     fn build_array(&mut self) -> Result<Json, BuilderError> {
2017         self.bump();
2018         let mut values = Vec::new();
2019
2020         loop {
2021             if self.token == Some(ArrayEnd) {
2022                 return Ok(Json::Array(values.into_iter().collect()));
2023             }
2024             match self.build_value() {
2025                 Ok(v) => values.push(v),
2026                 Err(e) => { return Err(e) }
2027             }
2028             self.bump();
2029         }
2030     }
2031
2032     fn build_object(&mut self) -> Result<Json, BuilderError> {
2033         self.bump();
2034
2035         let mut values = BTreeMap::new();
2036
2037         loop {
2038             match self.token {
2039                 Some(ObjectEnd) => { return Ok(Json::Object(values)); }
2040                 Some(Error(ref e)) => { return Err(e.clone()); }
2041                 None => { break; }
2042                 _ => {}
2043             }
2044             let key = match self.parser.stack().top() {
2045                 Some(StackElement::Key(k)) => { k.to_owned() }
2046                 _ => { panic!("invalid state"); }
2047             };
2048             match self.build_value() {
2049                 Ok(value) => { values.insert(key, value); }
2050                 Err(e) => { return Err(e); }
2051             }
2052             self.bump();
2053         }
2054         self.parser.error(EOFWhileParsingObject)
2055     }
2056 }
2057
2058 /// Decodes a json value from an `&mut io::Read`
2059 pub fn from_reader(rdr: &mut Read) -> Result<Json, BuilderError> {
2060     let mut contents = Vec::new();
2061     match rdr.read_to_end(&mut contents) {
2062         Ok(c)  => c,
2063         Err(e) => return Err(io_error_to_error(e))
2064     };
2065     let s = match str::from_utf8(&contents).ok() {
2066         Some(s) => s,
2067         _       => return Err(SyntaxError(NotUtf8, 0, 0))
2068     };
2069     let mut builder = Builder::new(s.chars());
2070     builder.build()
2071 }
2072
2073 /// Decodes a json value from a string
2074 pub fn from_str(s: &str) -> Result<Json, BuilderError> {
2075     let mut builder = Builder::new(s.chars());
2076     builder.build()
2077 }
2078
2079 /// A structure to decode JSON to values in rust.
2080 pub struct Decoder {
2081     stack: Vec<Json>,
2082 }
2083
2084 impl Decoder {
2085     /// Creates a new decoder instance for decoding the specified JSON value.
2086     pub fn new(json: Json) -> Decoder {
2087         Decoder { stack: vec![json] }
2088     }
2089
2090     fn pop(&mut self) -> Json {
2091         self.stack.pop().unwrap()
2092     }
2093 }
2094
2095 macro_rules! expect {
2096     ($e:expr, Null) => ({
2097         match $e {
2098             Json::Null => Ok(()),
2099             other => Err(ExpectedError("Null".to_owned(),
2100                                        format!("{}", other)))
2101         }
2102     });
2103     ($e:expr, $t:ident) => ({
2104         match $e {
2105             Json::$t(v) => Ok(v),
2106             other => {
2107                 Err(ExpectedError(stringify!($t).to_owned(),
2108                                   format!("{}", other)))
2109             }
2110         }
2111     })
2112 }
2113
2114 macro_rules! read_primitive {
2115     ($name:ident, $ty:ty) => {
2116         fn $name(&mut self) -> DecodeResult<$ty> {
2117             match self.pop() {
2118                 Json::I64(f) => Ok(f as $ty),
2119                 Json::U64(f) => Ok(f as $ty),
2120                 Json::F64(f) => Err(ExpectedError("Integer".to_owned(), format!("{}", f))),
2121                 // re: #12967.. a type w/ numeric keys (ie HashMap<usize, V> etc)
2122                 // is going to have a string here, as per JSON spec.
2123                 Json::String(s) => match s.parse().ok() {
2124                     Some(f) => Ok(f),
2125                     None => Err(ExpectedError("Number".to_owned(), s)),
2126                 },
2127                 value => Err(ExpectedError("Number".to_owned(), format!("{}", value))),
2128             }
2129         }
2130     }
2131 }
2132
2133 impl ::Decoder for Decoder {
2134     type Error = DecoderError;
2135
2136     fn read_nil(&mut self) -> DecodeResult<()> {
2137         expect!(self.pop(), Null)
2138     }
2139
2140     read_primitive! { read_usize, usize }
2141     read_primitive! { read_u8, u8 }
2142     read_primitive! { read_u16, u16 }
2143     read_primitive! { read_u32, u32 }
2144     read_primitive! { read_u64, u64 }
2145     read_primitive! { read_u128, u128 }
2146     read_primitive! { read_isize, isize }
2147     read_primitive! { read_i8, i8 }
2148     read_primitive! { read_i16, i16 }
2149     read_primitive! { read_i32, i32 }
2150     read_primitive! { read_i64, i64 }
2151     read_primitive! { read_i128, i128 }
2152
2153     fn read_f32(&mut self) -> DecodeResult<f32> { self.read_f64().map(|x| x as f32) }
2154
2155     fn read_f64(&mut self) -> DecodeResult<f64> {
2156         match self.pop() {
2157             Json::I64(f) => Ok(f as f64),
2158             Json::U64(f) => Ok(f as f64),
2159             Json::F64(f) => Ok(f),
2160             Json::String(s) => {
2161                 // re: #12967.. a type w/ numeric keys (ie HashMap<usize, V> etc)
2162                 // is going to have a string here, as per JSON spec.
2163                 match s.parse().ok() {
2164                     Some(f) => Ok(f),
2165                     None => Err(ExpectedError("Number".to_owned(), s)),
2166                 }
2167             },
2168             Json::Null => Ok(f64::NAN),
2169             value => Err(ExpectedError("Number".to_owned(), format!("{}", value)))
2170         }
2171     }
2172
2173     fn read_bool(&mut self) -> DecodeResult<bool> {
2174         expect!(self.pop(), Boolean)
2175     }
2176
2177     fn read_char(&mut self) -> DecodeResult<char> {
2178         let s = self.read_str()?;
2179         {
2180             let mut it = s.chars();
2181             match (it.next(), it.next()) {
2182                 // exactly one character
2183                 (Some(c), None) => return Ok(c),
2184                 _ => ()
2185             }
2186         }
2187         Err(ExpectedError("single character string".to_owned(), format!("{}", s)))
2188     }
2189
2190     fn read_str(&mut self) -> DecodeResult<Cow<str>> {
2191         expect!(self.pop(), String).map(Cow::Owned)
2192     }
2193
2194     fn read_enum<T, F>(&mut self, _name: &str, f: F) -> DecodeResult<T> where
2195         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2196     {
2197         f(self)
2198     }
2199
2200     fn read_enum_variant<T, F>(&mut self, names: &[&str],
2201                                mut f: F) -> DecodeResult<T>
2202         where F: FnMut(&mut Decoder, usize) -> DecodeResult<T>,
2203     {
2204         let name = match self.pop() {
2205             Json::String(s) => s,
2206             Json::Object(mut o) => {
2207                 let n = match o.remove(&"variant".to_owned()) {
2208                     Some(Json::String(s)) => s,
2209                     Some(val) => {
2210                         return Err(ExpectedError("String".to_owned(), format!("{}", val)))
2211                     }
2212                     None => {
2213                         return Err(MissingFieldError("variant".to_owned()))
2214                     }
2215                 };
2216                 match o.remove(&"fields".to_string()) {
2217                     Some(Json::Array(l)) => {
2218                         for field in l.into_iter().rev() {
2219                             self.stack.push(field);
2220                         }
2221                     },
2222                     Some(val) => {
2223                         return Err(ExpectedError("Array".to_owned(), format!("{}", val)))
2224                     }
2225                     None => {
2226                         return Err(MissingFieldError("fields".to_owned()))
2227                     }
2228                 }
2229                 n
2230             }
2231             json => {
2232                 return Err(ExpectedError("String or Object".to_owned(), format!("{}", json)))
2233             }
2234         };
2235         let idx = match names.iter().position(|n| *n == &name[..]) {
2236             Some(idx) => idx,
2237             None => return Err(UnknownVariantError(name))
2238         };
2239         f(self, idx)
2240     }
2241
2242     fn read_enum_variant_arg<T, F>(&mut self, _idx: usize, f: F) -> DecodeResult<T> where
2243         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2244     {
2245         f(self)
2246     }
2247
2248     fn read_enum_struct_variant<T, F>(&mut self, names: &[&str], f: F) -> DecodeResult<T> where
2249         F: FnMut(&mut Decoder, usize) -> DecodeResult<T>,
2250     {
2251         self.read_enum_variant(names, f)
2252     }
2253
2254
2255     fn read_enum_struct_variant_field<T, F>(&mut self,
2256                                          _name: &str,
2257                                          idx: usize,
2258                                          f: F)
2259                                          -> DecodeResult<T> where
2260         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2261     {
2262         self.read_enum_variant_arg(idx, f)
2263     }
2264
2265     fn read_struct<T, F>(&mut self, _name: &str, _len: usize, f: F) -> DecodeResult<T> where
2266         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2267     {
2268         let value = f(self)?;
2269         self.pop();
2270         Ok(value)
2271     }
2272
2273     fn read_struct_field<T, F>(&mut self,
2274                                name: &str,
2275                                _idx: usize,
2276                                f: F)
2277                                -> DecodeResult<T> where
2278         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2279     {
2280         let mut obj = expect!(self.pop(), Object)?;
2281
2282         let value = match obj.remove(&name.to_string()) {
2283             None => {
2284                 // Add a Null and try to parse it as an Option<_>
2285                 // to get None as a default value.
2286                 self.stack.push(Json::Null);
2287                 match f(self) {
2288                     Ok(x) => x,
2289                     Err(_) => return Err(MissingFieldError(name.to_string())),
2290                 }
2291             },
2292             Some(json) => {
2293                 self.stack.push(json);
2294                 f(self)?
2295             }
2296         };
2297         self.stack.push(Json::Object(obj));
2298         Ok(value)
2299     }
2300
2301     fn read_tuple<T, F>(&mut self, tuple_len: usize, f: F) -> DecodeResult<T> where
2302         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2303     {
2304         self.read_seq(move |d, len| {
2305             if len == tuple_len {
2306                 f(d)
2307             } else {
2308                 Err(ExpectedError(format!("Tuple{}", tuple_len), format!("Tuple{}", len)))
2309             }
2310         })
2311     }
2312
2313     fn read_tuple_arg<T, F>(&mut self, idx: usize, f: F) -> DecodeResult<T> where
2314         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2315     {
2316         self.read_seq_elt(idx, f)
2317     }
2318
2319     fn read_tuple_struct<T, F>(&mut self,
2320                                _name: &str,
2321                                len: usize,
2322                                f: F)
2323                                -> DecodeResult<T> where
2324         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2325     {
2326         self.read_tuple(len, f)
2327     }
2328
2329     fn read_tuple_struct_arg<T, F>(&mut self,
2330                                    idx: usize,
2331                                    f: F)
2332                                    -> DecodeResult<T> where
2333         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2334     {
2335         self.read_tuple_arg(idx, f)
2336     }
2337
2338     fn read_option<T, F>(&mut self, mut f: F) -> DecodeResult<T> where
2339         F: FnMut(&mut Decoder, bool) -> DecodeResult<T>,
2340     {
2341         match self.pop() {
2342             Json::Null => f(self, false),
2343             value => { self.stack.push(value); f(self, true) }
2344         }
2345     }
2346
2347     fn read_seq<T, F>(&mut self, f: F) -> DecodeResult<T> where
2348         F: FnOnce(&mut Decoder, usize) -> DecodeResult<T>,
2349     {
2350         let array = expect!(self.pop(), Array)?;
2351         let len = array.len();
2352         for v in array.into_iter().rev() {
2353             self.stack.push(v);
2354         }
2355         f(self, len)
2356     }
2357
2358     fn read_seq_elt<T, F>(&mut self, _idx: usize, f: F) -> DecodeResult<T> where
2359         F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2360     {
2361         f(self)
2362     }
2363
2364     fn read_map<T, F>(&mut self, f: F) -> DecodeResult<T> where
2365         F: FnOnce(&mut Decoder, usize) -> DecodeResult<T>,
2366     {
2367         let obj = expect!(self.pop(), Object)?;
2368         let len = obj.len();
2369         for (key, value) in obj {
2370             self.stack.push(value);
2371             self.stack.push(Json::String(key));
2372         }
2373         f(self, len)
2374     }
2375
2376     fn read_map_elt_key<T, F>(&mut self, _idx: usize, f: F) -> DecodeResult<T> where
2377        F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2378     {
2379         f(self)
2380     }
2381
2382     fn read_map_elt_val<T, F>(&mut self, _idx: usize, f: F) -> DecodeResult<T> where
2383        F: FnOnce(&mut Decoder) -> DecodeResult<T>,
2384     {
2385         f(self)
2386     }
2387
2388     fn error(&mut self, err: &str) -> DecoderError {
2389         ApplicationError(err.to_string())
2390     }
2391 }
2392
2393 /// A trait for converting values to JSON
2394 pub trait ToJson {
2395     /// Converts the value of `self` to an instance of JSON
2396     fn to_json(&self) -> Json;
2397 }
2398
2399 macro_rules! to_json_impl_i64 {
2400     ($($t:ty), +) => (
2401         $(impl ToJson for $t {
2402             fn to_json(&self) -> Json {
2403                 Json::I64(*self as i64)
2404             }
2405         })+
2406     )
2407 }
2408
2409 to_json_impl_i64! { isize, i8, i16, i32, i64 }
2410
2411 macro_rules! to_json_impl_u64 {
2412     ($($t:ty), +) => (
2413         $(impl ToJson for $t {
2414             fn to_json(&self) -> Json {
2415                 Json::U64(*self as u64)
2416             }
2417         })+
2418     )
2419 }
2420
2421 to_json_impl_u64! { usize, u8, u16, u32, u64 }
2422
2423 impl ToJson for Json {
2424     fn to_json(&self) -> Json { self.clone() }
2425 }
2426
2427 impl ToJson for f32 {
2428     fn to_json(&self) -> Json { (*self as f64).to_json() }
2429 }
2430
2431 impl ToJson for f64 {
2432     fn to_json(&self) -> Json {
2433         match self.classify() {
2434             Fp::Nan | Fp::Infinite => Json::Null,
2435             _                  => Json::F64(*self)
2436         }
2437     }
2438 }
2439
2440 impl ToJson for () {
2441     fn to_json(&self) -> Json { Json::Null }
2442 }
2443
2444 impl ToJson for bool {
2445     fn to_json(&self) -> Json { Json::Boolean(*self) }
2446 }
2447
2448 impl ToJson for str {
2449     fn to_json(&self) -> Json { Json::String(self.to_string()) }
2450 }
2451
2452 impl ToJson for string::String {
2453     fn to_json(&self) -> Json { Json::String((*self).clone()) }
2454 }
2455
2456 macro_rules! tuple_impl {
2457     // use variables to indicate the arity of the tuple
2458     ($($tyvar:ident),* ) => {
2459         // the trailing commas are for the 1 tuple
2460         impl<
2461             $( $tyvar : ToJson ),*
2462             > ToJson for ( $( $tyvar ),* , ) {
2463
2464             #[inline]
2465             #[allow(non_snake_case)]
2466             fn to_json(&self) -> Json {
2467                 match *self {
2468                     ($(ref $tyvar),*,) => Json::Array(vec![$($tyvar.to_json()),*])
2469                 }
2470             }
2471         }
2472     }
2473 }
2474
2475 tuple_impl!{A}
2476 tuple_impl!{A, B}
2477 tuple_impl!{A, B, C}
2478 tuple_impl!{A, B, C, D}
2479 tuple_impl!{A, B, C, D, E}
2480 tuple_impl!{A, B, C, D, E, F}
2481 tuple_impl!{A, B, C, D, E, F, G}
2482 tuple_impl!{A, B, C, D, E, F, G, H}
2483 tuple_impl!{A, B, C, D, E, F, G, H, I}
2484 tuple_impl!{A, B, C, D, E, F, G, H, I, J}
2485 tuple_impl!{A, B, C, D, E, F, G, H, I, J, K}
2486 tuple_impl!{A, B, C, D, E, F, G, H, I, J, K, L}
2487
2488 impl<A: ToJson> ToJson for [A] {
2489     fn to_json(&self) -> Json { Json::Array(self.iter().map(|elt| elt.to_json()).collect()) }
2490 }
2491
2492 impl<A: ToJson> ToJson for Vec<A> {
2493     fn to_json(&self) -> Json { Json::Array(self.iter().map(|elt| elt.to_json()).collect()) }
2494 }
2495
2496 impl<A: ToJson> ToJson for BTreeMap<string::String, A> {
2497     fn to_json(&self) -> Json {
2498         let mut d = BTreeMap::new();
2499         for (key, value) in self {
2500             d.insert((*key).clone(), value.to_json());
2501         }
2502         Json::Object(d)
2503     }
2504 }
2505
2506 impl<A: ToJson> ToJson for HashMap<string::String, A> {
2507     fn to_json(&self) -> Json {
2508         let mut d = BTreeMap::new();
2509         for (key, value) in self {
2510             d.insert((*key).clone(), value.to_json());
2511         }
2512         Json::Object(d)
2513     }
2514 }
2515
2516 impl<A:ToJson> ToJson for Option<A> {
2517     fn to_json(&self) -> Json {
2518         match *self {
2519             None => Json::Null,
2520             Some(ref value) => value.to_json()
2521         }
2522     }
2523 }
2524
2525 struct FormatShim<'a, 'b: 'a> {
2526     inner: &'a mut fmt::Formatter<'b>,
2527 }
2528
2529 impl<'a, 'b> fmt::Write for FormatShim<'a, 'b> {
2530     fn write_str(&mut self, s: &str) -> fmt::Result {
2531         match self.inner.write_str(s) {
2532             Ok(_) => Ok(()),
2533             Err(_) => Err(fmt::Error)
2534         }
2535     }
2536 }
2537
2538 impl fmt::Display for Json {
2539     /// Encodes a json value into a string
2540     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2541         let mut shim = FormatShim { inner: f };
2542         let mut encoder = Encoder::new(&mut shim);
2543         match self.encode(&mut encoder) {
2544             Ok(_) => Ok(()),
2545             Err(_) => Err(fmt::Error)
2546         }
2547     }
2548 }
2549
2550 impl<'a> fmt::Display for PrettyJson<'a> {
2551     /// Encodes a json value into a string
2552     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2553         let mut shim = FormatShim { inner: f };
2554         let mut encoder = PrettyEncoder::new(&mut shim);
2555         match self.inner.encode(&mut encoder) {
2556             Ok(_) => Ok(()),
2557             Err(_) => Err(fmt::Error)
2558         }
2559     }
2560 }
2561
2562 impl<'a, T: Encodable> fmt::Display for AsJson<'a, T> {
2563     /// Encodes a json value into a string
2564     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2565         let mut shim = FormatShim { inner: f };
2566         let mut encoder = Encoder::new(&mut shim);
2567         match self.inner.encode(&mut encoder) {
2568             Ok(_) => Ok(()),
2569             Err(_) => Err(fmt::Error)
2570         }
2571     }
2572 }
2573
2574 impl<'a, T> AsPrettyJson<'a, T> {
2575     /// Set the indentation level for the emitted JSON
2576     pub fn indent(mut self, indent: usize) -> AsPrettyJson<'a, T> {
2577         self.indent = Some(indent);
2578         self
2579     }
2580 }
2581
2582 impl<'a, T: Encodable> fmt::Display for AsPrettyJson<'a, T> {
2583     /// Encodes a json value into a string
2584     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2585         let mut shim = FormatShim { inner: f };
2586         let mut encoder = PrettyEncoder::new(&mut shim);
2587         if let Some(n) = self.indent {
2588             encoder.set_indent(n);
2589         }
2590         match self.inner.encode(&mut encoder) {
2591             Ok(_) => Ok(()),
2592             Err(_) => Err(fmt::Error)
2593         }
2594     }
2595 }
2596
2597 impl FromStr for Json {
2598     type Err = BuilderError;
2599     fn from_str(s: &str) -> Result<Json, BuilderError> {
2600         from_str(s)
2601     }
2602 }
2603
2604 #[cfg(test)]
2605 mod tests {
2606     extern crate test;
2607     use self::Animal::*;
2608     use self::test::Bencher;
2609     use {Encodable, Decodable};
2610     use super::Json::*;
2611     use super::ErrorCode::*;
2612     use super::ParserError::*;
2613     use super::DecoderError::*;
2614     use super::JsonEvent::*;
2615     use super::{Json, from_str, DecodeResult, DecoderError, JsonEvent, Parser,
2616                 StackElement, Stack, Decoder, Encoder, EncoderError};
2617     use std::{i64, u64, f32, f64};
2618     use std::io::prelude::*;
2619     use std::collections::BTreeMap;
2620     use std::string;
2621
2622     #[derive(RustcDecodable, Eq, PartialEq, Debug)]
2623     struct OptionData {
2624         opt: Option<usize>,
2625     }
2626
2627     #[test]
2628     fn test_decode_option_none() {
2629         let s ="{}";
2630         let obj: OptionData = super::decode(s).unwrap();
2631         assert_eq!(obj, OptionData { opt: None });
2632     }
2633
2634     #[test]
2635     fn test_decode_option_some() {
2636         let s = "{ \"opt\": 10 }";
2637         let obj: OptionData = super::decode(s).unwrap();
2638         assert_eq!(obj, OptionData { opt: Some(10) });
2639     }
2640
2641     #[test]
2642     fn test_decode_option_malformed() {
2643         check_err::<OptionData>("{ \"opt\": [] }",
2644                                 ExpectedError("Number".to_string(), "[]".to_string()));
2645         check_err::<OptionData>("{ \"opt\": false }",
2646                                 ExpectedError("Number".to_string(), "false".to_string()));
2647     }
2648
2649     #[derive(PartialEq, RustcEncodable, RustcDecodable, Debug)]
2650     enum Animal {
2651         Dog,
2652         Frog(string::String, isize)
2653     }
2654
2655     #[derive(PartialEq, RustcEncodable, RustcDecodable, Debug)]
2656     struct Inner {
2657         a: (),
2658         b: usize,
2659         c: Vec<string::String>,
2660     }
2661
2662     #[derive(PartialEq, RustcEncodable, RustcDecodable, Debug)]
2663     struct Outer {
2664         inner: Vec<Inner>,
2665     }
2666
2667     fn mk_object(items: &[(string::String, Json)]) -> Json {
2668         let mut d = BTreeMap::new();
2669
2670         for item in items {
2671             match *item {
2672                 (ref key, ref value) => { d.insert((*key).clone(), (*value).clone()); },
2673             }
2674         };
2675
2676         Object(d)
2677     }
2678
2679     #[test]
2680     fn test_from_str_trait() {
2681         let s = "null";
2682         assert!(s.parse::<Json>().unwrap() == s.parse().unwrap());
2683     }
2684
2685     #[test]
2686     fn test_write_null() {
2687         assert_eq!(Null.to_string(), "null");
2688         assert_eq!(Null.pretty().to_string(), "null");
2689     }
2690
2691     #[test]
2692     fn test_write_i64() {
2693         assert_eq!(U64(0).to_string(), "0");
2694         assert_eq!(U64(0).pretty().to_string(), "0");
2695
2696         assert_eq!(U64(1234).to_string(), "1234");
2697         assert_eq!(U64(1234).pretty().to_string(), "1234");
2698
2699         assert_eq!(I64(-5678).to_string(), "-5678");
2700         assert_eq!(I64(-5678).pretty().to_string(), "-5678");
2701
2702         assert_eq!(U64(7650007200025252000).to_string(), "7650007200025252000");
2703         assert_eq!(U64(7650007200025252000).pretty().to_string(), "7650007200025252000");
2704     }
2705
2706     #[test]
2707     fn test_write_f64() {
2708         assert_eq!(F64(3.0).to_string(), "3.0");
2709         assert_eq!(F64(3.0).pretty().to_string(), "3.0");
2710
2711         assert_eq!(F64(3.1).to_string(), "3.1");
2712         assert_eq!(F64(3.1).pretty().to_string(), "3.1");
2713
2714         assert_eq!(F64(-1.5).to_string(), "-1.5");
2715         assert_eq!(F64(-1.5).pretty().to_string(), "-1.5");
2716
2717         assert_eq!(F64(0.5).to_string(), "0.5");
2718         assert_eq!(F64(0.5).pretty().to_string(), "0.5");
2719
2720         assert_eq!(F64(f64::NAN).to_string(), "null");
2721         assert_eq!(F64(f64::NAN).pretty().to_string(), "null");
2722
2723         assert_eq!(F64(f64::INFINITY).to_string(), "null");
2724         assert_eq!(F64(f64::INFINITY).pretty().to_string(), "null");
2725
2726         assert_eq!(F64(f64::NEG_INFINITY).to_string(), "null");
2727         assert_eq!(F64(f64::NEG_INFINITY).pretty().to_string(), "null");
2728     }
2729
2730     #[test]
2731     fn test_write_str() {
2732         assert_eq!(String("".to_string()).to_string(), "\"\"");
2733         assert_eq!(String("".to_string()).pretty().to_string(), "\"\"");
2734
2735         assert_eq!(String("homura".to_string()).to_string(), "\"homura\"");
2736         assert_eq!(String("madoka".to_string()).pretty().to_string(), "\"madoka\"");
2737     }
2738
2739     #[test]
2740     fn test_write_bool() {
2741         assert_eq!(Boolean(true).to_string(), "true");
2742         assert_eq!(Boolean(true).pretty().to_string(), "true");
2743
2744         assert_eq!(Boolean(false).to_string(), "false");
2745         assert_eq!(Boolean(false).pretty().to_string(), "false");
2746     }
2747
2748     #[test]
2749     fn test_write_array() {
2750         assert_eq!(Array(vec![]).to_string(), "[]");
2751         assert_eq!(Array(vec![]).pretty().to_string(), "[]");
2752
2753         assert_eq!(Array(vec![Boolean(true)]).to_string(), "[true]");
2754         assert_eq!(
2755             Array(vec![Boolean(true)]).pretty().to_string(),
2756             "\
2757             [\n  \
2758                 true\n\
2759             ]"
2760         );
2761
2762         let long_test_array = Array(vec![
2763             Boolean(false),
2764             Null,
2765             Array(vec![String("foo\nbar".to_string()), F64(3.5)])]);
2766
2767         assert_eq!(long_test_array.to_string(),
2768             "[false,null,[\"foo\\nbar\",3.5]]");
2769         assert_eq!(
2770             long_test_array.pretty().to_string(),
2771             "\
2772             [\n  \
2773                 false,\n  \
2774                 null,\n  \
2775                 [\n    \
2776                     \"foo\\nbar\",\n    \
2777                     3.5\n  \
2778                 ]\n\
2779             ]"
2780         );
2781     }
2782
2783     #[test]
2784     fn test_write_object() {
2785         assert_eq!(mk_object(&[]).to_string(), "{}");
2786         assert_eq!(mk_object(&[]).pretty().to_string(), "{}");
2787
2788         assert_eq!(
2789             mk_object(&[
2790                 ("a".to_string(), Boolean(true))
2791             ]).to_string(),
2792             "{\"a\":true}"
2793         );
2794         assert_eq!(
2795             mk_object(&[("a".to_string(), Boolean(true))]).pretty().to_string(),
2796             "\
2797             {\n  \
2798                 \"a\": true\n\
2799             }"
2800         );
2801
2802         let complex_obj = mk_object(&[
2803                 ("b".to_string(), Array(vec![
2804                     mk_object(&[("c".to_string(), String("\x0c\r".to_string()))]),
2805                     mk_object(&[("d".to_string(), String("".to_string()))])
2806                 ]))
2807             ]);
2808
2809         assert_eq!(
2810             complex_obj.to_string(),
2811             "{\
2812                 \"b\":[\
2813                     {\"c\":\"\\f\\r\"},\
2814                     {\"d\":\"\"}\
2815                 ]\
2816             }"
2817         );
2818         assert_eq!(
2819             complex_obj.pretty().to_string(),
2820             "\
2821             {\n  \
2822                 \"b\": [\n    \
2823                     {\n      \
2824                         \"c\": \"\\f\\r\"\n    \
2825                     },\n    \
2826                     {\n      \
2827                         \"d\": \"\"\n    \
2828                     }\n  \
2829                 ]\n\
2830             }"
2831         );
2832
2833         let a = mk_object(&[
2834             ("a".to_string(), Boolean(true)),
2835             ("b".to_string(), Array(vec![
2836                 mk_object(&[("c".to_string(), String("\x0c\r".to_string()))]),
2837                 mk_object(&[("d".to_string(), String("".to_string()))])
2838             ]))
2839         ]);
2840
2841         // We can't compare the strings directly because the object fields be
2842         // printed in a different order.
2843         assert_eq!(a.clone(), a.to_string().parse().unwrap());
2844         assert_eq!(a.clone(), a.pretty().to_string().parse().unwrap());
2845     }
2846
2847     #[test]
2848     fn test_write_enum() {
2849         let animal = Dog;
2850         assert_eq!(
2851             format!("{}", super::as_json(&animal)),
2852             "\"Dog\""
2853         );
2854         assert_eq!(
2855             format!("{}", super::as_pretty_json(&animal)),
2856             "\"Dog\""
2857         );
2858
2859         let animal = Frog("Henry".to_string(), 349);
2860         assert_eq!(
2861             format!("{}", super::as_json(&animal)),
2862             "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}"
2863         );
2864         assert_eq!(
2865             format!("{}", super::as_pretty_json(&animal)),
2866             "{\n  \
2867                \"variant\": \"Frog\",\n  \
2868                \"fields\": [\n    \
2869                  \"Henry\",\n    \
2870                  349\n  \
2871                ]\n\
2872              }"
2873         );
2874     }
2875
2876     macro_rules! check_encoder_for_simple {
2877         ($value:expr, $expected:expr) => ({
2878             let s = format!("{}", super::as_json(&$value));
2879             assert_eq!(s, $expected);
2880
2881             let s = format!("{}", super::as_pretty_json(&$value));
2882             assert_eq!(s, $expected);
2883         })
2884     }
2885
2886     #[test]
2887     fn test_write_some() {
2888         check_encoder_for_simple!(Some("jodhpurs".to_string()), "\"jodhpurs\"");
2889     }
2890
2891     #[test]
2892     fn test_write_none() {
2893         check_encoder_for_simple!(None::<string::String>, "null");
2894     }
2895
2896     #[test]
2897     fn test_write_char() {
2898         check_encoder_for_simple!('a', "\"a\"");
2899         check_encoder_for_simple!('\t', "\"\\t\"");
2900         check_encoder_for_simple!('\u{0000}', "\"\\u0000\"");
2901         check_encoder_for_simple!('\u{001b}', "\"\\u001b\"");
2902         check_encoder_for_simple!('\u{007f}', "\"\\u007f\"");
2903         check_encoder_for_simple!('\u{00a0}', "\"\u{00a0}\"");
2904         check_encoder_for_simple!('\u{abcd}', "\"\u{abcd}\"");
2905         check_encoder_for_simple!('\u{10ffff}', "\"\u{10ffff}\"");
2906     }
2907
2908     #[test]
2909     fn test_trailing_characters() {
2910         assert_eq!(from_str("nulla"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2911         assert_eq!(from_str("truea"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2912         assert_eq!(from_str("falsea"), Err(SyntaxError(TrailingCharacters, 1, 6)));
2913         assert_eq!(from_str("1a"),     Err(SyntaxError(TrailingCharacters, 1, 2)));
2914         assert_eq!(from_str("[]a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2915         assert_eq!(from_str("{}a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2916     }
2917
2918     #[test]
2919     fn test_read_identifiers() {
2920         assert_eq!(from_str("n"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2921         assert_eq!(from_str("nul"),  Err(SyntaxError(InvalidSyntax, 1, 4)));
2922         assert_eq!(from_str("t"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2923         assert_eq!(from_str("truz"), Err(SyntaxError(InvalidSyntax, 1, 4)));
2924         assert_eq!(from_str("f"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2925         assert_eq!(from_str("faz"),  Err(SyntaxError(InvalidSyntax, 1, 3)));
2926
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         assert_eq!(from_str(" null "), Ok(Null));
2931         assert_eq!(from_str(" true "), Ok(Boolean(true)));
2932         assert_eq!(from_str(" false "), Ok(Boolean(false)));
2933     }
2934
2935     #[test]
2936     fn test_decode_identifiers() {
2937         let v: () = super::decode("null").unwrap();
2938         assert_eq!(v, ());
2939
2940         let v: bool = super::decode("true").unwrap();
2941         assert_eq!(v, true);
2942
2943         let v: bool = super::decode("false").unwrap();
2944         assert_eq!(v, false);
2945     }
2946
2947     #[test]
2948     fn test_read_number() {
2949         assert_eq!(from_str("+"),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2950         assert_eq!(from_str("."),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2951         assert_eq!(from_str("NaN"), Err(SyntaxError(InvalidSyntax, 1, 1)));
2952         assert_eq!(from_str("-"),   Err(SyntaxError(InvalidNumber, 1, 2)));
2953         assert_eq!(from_str("00"),  Err(SyntaxError(InvalidNumber, 1, 2)));
2954         assert_eq!(from_str("1."),  Err(SyntaxError(InvalidNumber, 1, 3)));
2955         assert_eq!(from_str("1e"),  Err(SyntaxError(InvalidNumber, 1, 3)));
2956         assert_eq!(from_str("1e+"), Err(SyntaxError(InvalidNumber, 1, 4)));
2957
2958         assert_eq!(from_str("18446744073709551616"), Err(SyntaxError(InvalidNumber, 1, 20)));
2959         assert_eq!(from_str("-9223372036854775809"), Err(SyntaxError(InvalidNumber, 1, 21)));
2960
2961         assert_eq!(from_str("3"), Ok(U64(3)));
2962         assert_eq!(from_str("3.1"), Ok(F64(3.1)));
2963         assert_eq!(from_str("-1.2"), Ok(F64(-1.2)));
2964         assert_eq!(from_str("0.4"), Ok(F64(0.4)));
2965         assert_eq!(from_str("0.4e5"), Ok(F64(0.4e5)));
2966         assert_eq!(from_str("0.4e+15"), Ok(F64(0.4e15)));
2967         assert_eq!(from_str("0.4e-01"), Ok(F64(0.4e-01)));
2968         assert_eq!(from_str(" 3 "), Ok(U64(3)));
2969
2970         assert_eq!(from_str("-9223372036854775808"), Ok(I64(i64::MIN)));
2971         assert_eq!(from_str("9223372036854775807"), Ok(U64(i64::MAX as u64)));
2972         assert_eq!(from_str("18446744073709551615"), Ok(U64(u64::MAX)));
2973     }
2974
2975     #[test]
2976     fn test_decode_numbers() {
2977         let v: f64 = super::decode("3").unwrap();
2978         assert_eq!(v, 3.0);
2979
2980         let v: f64 = super::decode("3.1").unwrap();
2981         assert_eq!(v, 3.1);
2982
2983         let v: f64 = super::decode("-1.2").unwrap();
2984         assert_eq!(v, -1.2);
2985
2986         let v: f64 = super::decode("0.4").unwrap();
2987         assert_eq!(v, 0.4);
2988
2989         let v: f64 = super::decode("0.4e5").unwrap();
2990         assert_eq!(v, 0.4e5);
2991
2992         let v: f64 = super::decode("0.4e15").unwrap();
2993         assert_eq!(v, 0.4e15);
2994
2995         let v: f64 = super::decode("0.4e-01").unwrap();
2996         assert_eq!(v, 0.4e-01);
2997
2998         let v: u64 = super::decode("0").unwrap();
2999         assert_eq!(v, 0);
3000
3001         let v: u64 = super::decode("18446744073709551615").unwrap();
3002         assert_eq!(v, u64::MAX);
3003
3004         let v: i64 = super::decode("-9223372036854775808").unwrap();
3005         assert_eq!(v, i64::MIN);
3006
3007         let v: i64 = super::decode("9223372036854775807").unwrap();
3008         assert_eq!(v, i64::MAX);
3009
3010         let res: DecodeResult<i64> = super::decode("765.25");
3011         assert_eq!(res, Err(ExpectedError("Integer".to_string(),
3012                                           "765.25".to_string())));
3013     }
3014
3015     #[test]
3016     fn test_read_str() {
3017         assert_eq!(from_str("\""),    Err(SyntaxError(EOFWhileParsingString, 1, 2)));
3018         assert_eq!(from_str("\"lol"), Err(SyntaxError(EOFWhileParsingString, 1, 5)));
3019
3020         assert_eq!(from_str("\"\""), Ok(String("".to_string())));
3021         assert_eq!(from_str("\"foo\""), Ok(String("foo".to_string())));
3022         assert_eq!(from_str("\"\\\"\""), Ok(String("\"".to_string())));
3023         assert_eq!(from_str("\"\\b\""), Ok(String("\x08".to_string())));
3024         assert_eq!(from_str("\"\\n\""), Ok(String("\n".to_string())));
3025         assert_eq!(from_str("\"\\r\""), Ok(String("\r".to_string())));
3026         assert_eq!(from_str("\"\\t\""), Ok(String("\t".to_string())));
3027         assert_eq!(from_str(" \"foo\" "), Ok(String("foo".to_string())));
3028         assert_eq!(from_str("\"\\u12ab\""), Ok(String("\u{12ab}".to_string())));
3029         assert_eq!(from_str("\"\\uAB12\""), Ok(String("\u{AB12}".to_string())));
3030     }
3031
3032     #[test]
3033     fn test_decode_str() {
3034         let s = [("\"\"", ""),
3035                  ("\"foo\"", "foo"),
3036                  ("\"\\\"\"", "\""),
3037                  ("\"\\b\"", "\x08"),
3038                  ("\"\\n\"", "\n"),
3039                  ("\"\\r\"", "\r"),
3040                  ("\"\\t\"", "\t"),
3041                  ("\"\\u12ab\"", "\u{12ab}"),
3042                  ("\"\\uAB12\"", "\u{AB12}")];
3043
3044         for &(i, o) in &s {
3045             let v: string::String = super::decode(i).unwrap();
3046             assert_eq!(v, o);
3047         }
3048     }
3049
3050     #[test]
3051     fn test_read_array() {
3052         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
3053         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingArray, 1, 3)));
3054         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
3055         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
3056         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
3057
3058         assert_eq!(from_str("[]"), Ok(Array(vec![])));
3059         assert_eq!(from_str("[ ]"), Ok(Array(vec![])));
3060         assert_eq!(from_str("[true]"), Ok(Array(vec![Boolean(true)])));
3061         assert_eq!(from_str("[ false ]"), Ok(Array(vec![Boolean(false)])));
3062         assert_eq!(from_str("[null]"), Ok(Array(vec![Null])));
3063         assert_eq!(from_str("[3, 1]"),
3064                      Ok(Array(vec![U64(3), U64(1)])));
3065         assert_eq!(from_str("\n[3, 2]\n"),
3066                      Ok(Array(vec![U64(3), U64(2)])));
3067         assert_eq!(from_str("[2, [4, 1]]"),
3068                Ok(Array(vec![U64(2), Array(vec![U64(4), U64(1)])])));
3069     }
3070
3071     #[test]
3072     fn test_decode_array() {
3073         let v: Vec<()> = super::decode("[]").unwrap();
3074         assert_eq!(v, []);
3075
3076         let v: Vec<()> = super::decode("[null]").unwrap();
3077         assert_eq!(v, [()]);
3078
3079         let v: Vec<bool> = super::decode("[true]").unwrap();
3080         assert_eq!(v, [true]);
3081
3082         let v: Vec<isize> = super::decode("[3, 1]").unwrap();
3083         assert_eq!(v, [3, 1]);
3084
3085         let v: Vec<Vec<usize>> = super::decode("[[3], [1, 2]]").unwrap();
3086         assert_eq!(v, [vec![3], vec![1, 2]]);
3087     }
3088
3089     #[test]
3090     fn test_decode_tuple() {
3091         let t: (usize, usize, usize) = super::decode("[1, 2, 3]").unwrap();
3092         assert_eq!(t, (1, 2, 3));
3093
3094         let t: (usize, string::String) = super::decode("[1, \"two\"]").unwrap();
3095         assert_eq!(t, (1, "two".to_string()));
3096     }
3097
3098     #[test]
3099     fn test_decode_tuple_malformed_types() {
3100         assert!(super::decode::<(usize, string::String)>("[1, 2]").is_err());
3101     }
3102
3103     #[test]
3104     fn test_decode_tuple_malformed_length() {
3105         assert!(super::decode::<(usize, usize)>("[1, 2, 3]").is_err());
3106     }
3107
3108     #[test]
3109     fn test_read_object() {
3110         assert_eq!(from_str("{"),       Err(SyntaxError(EOFWhileParsingObject, 1, 2)));
3111         assert_eq!(from_str("{ "),      Err(SyntaxError(EOFWhileParsingObject, 1, 3)));
3112         assert_eq!(from_str("{1"),      Err(SyntaxError(KeyMustBeAString,      1, 2)));
3113         assert_eq!(from_str("{ \"a\""), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
3114         assert_eq!(from_str("{\"a\""),  Err(SyntaxError(EOFWhileParsingObject, 1, 5)));
3115         assert_eq!(from_str("{\"a\" "), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
3116
3117         assert_eq!(from_str("{\"a\" 1"),   Err(SyntaxError(ExpectedColon,         1, 6)));
3118         assert_eq!(from_str("{\"a\":"),    Err(SyntaxError(EOFWhileParsingValue,  1, 6)));
3119         assert_eq!(from_str("{\"a\":1"),   Err(SyntaxError(EOFWhileParsingObject, 1, 7)));
3120         assert_eq!(from_str("{\"a\":1 1"), Err(SyntaxError(InvalidSyntax,         1, 8)));
3121         assert_eq!(from_str("{\"a\":1,"),  Err(SyntaxError(EOFWhileParsingObject, 1, 8)));
3122
3123         assert_eq!(from_str("{}").unwrap(), mk_object(&[]));
3124         assert_eq!(from_str("{\"a\": 3}").unwrap(),
3125                   mk_object(&[("a".to_string(), U64(3))]));
3126
3127         assert_eq!(from_str(
3128                       "{ \"a\": null, \"b\" : true }").unwrap(),
3129                   mk_object(&[
3130                       ("a".to_string(), Null),
3131                       ("b".to_string(), Boolean(true))]));
3132         assert_eq!(from_str("\n{ \"a\": null, \"b\" : true }\n").unwrap(),
3133                   mk_object(&[
3134                       ("a".to_string(), Null),
3135                       ("b".to_string(), Boolean(true))]));
3136         assert_eq!(from_str(
3137                       "{\"a\" : 1.0 ,\"b\": [ true ]}").unwrap(),
3138                   mk_object(&[
3139                       ("a".to_string(), F64(1.0)),
3140                       ("b".to_string(), Array(vec![Boolean(true)]))
3141                   ]));
3142         assert_eq!(from_str(
3143                       "{\
3144                           \"a\": 1.0, \
3145                           \"b\": [\
3146                               true,\
3147                               \"foo\\nbar\", \
3148                               { \"c\": {\"d\": null} } \
3149                           ]\
3150                       }").unwrap(),
3151                   mk_object(&[
3152                       ("a".to_string(), F64(1.0)),
3153                       ("b".to_string(), Array(vec![
3154                           Boolean(true),
3155                           String("foo\nbar".to_string()),
3156                           mk_object(&[
3157                               ("c".to_string(), mk_object(&[("d".to_string(), Null)]))
3158                           ])
3159                       ]))
3160                   ]));
3161     }
3162
3163     #[test]
3164     fn test_decode_struct() {
3165         let s = "{
3166             \"inner\": [
3167                 { \"a\": null, \"b\": 2, \"c\": [\"abc\", \"xyz\"] }
3168             ]
3169         }";
3170
3171         let v: Outer = super::decode(s).unwrap();
3172         assert_eq!(
3173             v,
3174             Outer {
3175                 inner: vec![
3176                     Inner { a: (), b: 2, c: vec!["abc".to_string(), "xyz".to_string()] }
3177                 ]
3178             }
3179         );
3180     }
3181
3182     #[derive(RustcDecodable)]
3183     struct FloatStruct {
3184         f: f64,
3185         a: Vec<f64>
3186     }
3187     #[test]
3188     fn test_decode_struct_with_nan() {
3189         let s = "{\"f\":null,\"a\":[null,123]}";
3190         let obj: FloatStruct = super::decode(s).unwrap();
3191         assert!(obj.f.is_nan());
3192         assert!(obj.a[0].is_nan());
3193         assert_eq!(obj.a[1], 123f64);
3194     }
3195
3196     #[test]
3197     fn test_decode_option() {
3198         let value: Option<string::String> = super::decode("null").unwrap();
3199         assert_eq!(value, None);
3200
3201         let value: Option<string::String> = super::decode("\"jodhpurs\"").unwrap();
3202         assert_eq!(value, Some("jodhpurs".to_string()));
3203     }
3204
3205     #[test]
3206     fn test_decode_enum() {
3207         let value: Animal = super::decode("\"Dog\"").unwrap();
3208         assert_eq!(value, Dog);
3209
3210         let s = "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}";
3211         let value: Animal = super::decode(s).unwrap();
3212         assert_eq!(value, Frog("Henry".to_string(), 349));
3213     }
3214
3215     #[test]
3216     fn test_decode_map() {
3217         let s = "{\"a\": \"Dog\", \"b\": {\"variant\":\"Frog\",\
3218                   \"fields\":[\"Henry\", 349]}}";
3219         let mut map: BTreeMap<string::String, Animal> = super::decode(s).unwrap();
3220
3221         assert_eq!(map.remove(&"a".to_string()), Some(Dog));
3222         assert_eq!(map.remove(&"b".to_string()), Some(Frog("Henry".to_string(), 349)));
3223     }
3224
3225     #[test]
3226     fn test_multiline_errors() {
3227         assert_eq!(from_str("{\n  \"foo\":\n \"bar\""),
3228             Err(SyntaxError(EOFWhileParsingObject, 3, 8)));
3229     }
3230
3231     #[derive(RustcDecodable)]
3232     #[allow(dead_code)]
3233     struct DecodeStruct {
3234         x: f64,
3235         y: bool,
3236         z: string::String,
3237         w: Vec<DecodeStruct>
3238     }
3239     #[derive(RustcDecodable)]
3240     enum DecodeEnum {
3241         A(f64),
3242         B(string::String)
3243     }
3244     fn check_err<T: Decodable>(to_parse: &'static str, expected: DecoderError) {
3245         let res: DecodeResult<T> = match from_str(to_parse) {
3246             Err(e) => Err(ParseError(e)),
3247             Ok(json) => Decodable::decode(&mut Decoder::new(json))
3248         };
3249         match res {
3250             Ok(_) => panic!("`{:?}` parsed & decoded ok, expecting error `{:?}`",
3251                               to_parse, expected),
3252             Err(ParseError(e)) => panic!("`{:?}` is not valid json: {:?}",
3253                                            to_parse, e),
3254             Err(e) => {
3255                 assert_eq!(e, expected);
3256             }
3257         }
3258     }
3259     #[test]
3260     fn test_decode_errors_struct() {
3261         check_err::<DecodeStruct>("[]", ExpectedError("Object".to_string(), "[]".to_string()));
3262         check_err::<DecodeStruct>("{\"x\": true, \"y\": true, \"z\": \"\", \"w\": []}",
3263                                   ExpectedError("Number".to_string(), "true".to_string()));
3264         check_err::<DecodeStruct>("{\"x\": 1, \"y\": [], \"z\": \"\", \"w\": []}",
3265                                   ExpectedError("Boolean".to_string(), "[]".to_string()));
3266         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": {}, \"w\": []}",
3267                                   ExpectedError("String".to_string(), "{}".to_string()));
3268         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\", \"w\": null}",
3269                                   ExpectedError("Array".to_string(), "null".to_string()));
3270         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\"}",
3271                                   MissingFieldError("w".to_string()));
3272     }
3273     #[test]
3274     fn test_decode_errors_enum() {
3275         check_err::<DecodeEnum>("{}",
3276                                 MissingFieldError("variant".to_string()));
3277         check_err::<DecodeEnum>("{\"variant\": 1}",
3278                                 ExpectedError("String".to_string(), "1".to_string()));
3279         check_err::<DecodeEnum>("{\"variant\": \"A\"}",
3280                                 MissingFieldError("fields".to_string()));
3281         check_err::<DecodeEnum>("{\"variant\": \"A\", \"fields\": null}",
3282                                 ExpectedError("Array".to_string(), "null".to_string()));
3283         check_err::<DecodeEnum>("{\"variant\": \"C\", \"fields\": []}",
3284                                 UnknownVariantError("C".to_string()));
3285     }
3286
3287     #[test]
3288     fn test_find(){
3289         let json_value = from_str("{\"dog\" : \"cat\"}").unwrap();
3290         let found_str = json_value.find("dog");
3291         assert!(found_str.unwrap().as_string().unwrap() == "cat");
3292     }
3293
3294     #[test]
3295     fn test_find_path(){
3296         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
3297         let found_str = json_value.find_path(&["dog", "cat", "mouse"]);
3298         assert!(found_str.unwrap().as_string().unwrap() == "cheese");
3299     }
3300
3301     #[test]
3302     fn test_search(){
3303         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
3304         let found_str = json_value.search("mouse").and_then(|j| j.as_string());
3305         assert!(found_str.unwrap() == "cheese");
3306     }
3307
3308     #[test]
3309     fn test_index(){
3310         let json_value = from_str("{\"animals\":[\"dog\",\"cat\",\"mouse\"]}").unwrap();
3311         let ref array = json_value["animals"];
3312         assert_eq!(array[0].as_string().unwrap(), "dog");
3313         assert_eq!(array[1].as_string().unwrap(), "cat");
3314         assert_eq!(array[2].as_string().unwrap(), "mouse");
3315     }
3316
3317     #[test]
3318     fn test_is_object(){
3319         let json_value = from_str("{}").unwrap();
3320         assert!(json_value.is_object());
3321     }
3322
3323     #[test]
3324     fn test_as_object(){
3325         let json_value = from_str("{}").unwrap();
3326         let json_object = json_value.as_object();
3327         assert!(json_object.is_some());
3328     }
3329
3330     #[test]
3331     fn test_is_array(){
3332         let json_value = from_str("[1, 2, 3]").unwrap();
3333         assert!(json_value.is_array());
3334     }
3335
3336     #[test]
3337     fn test_as_array(){
3338         let json_value = from_str("[1, 2, 3]").unwrap();
3339         let json_array = json_value.as_array();
3340         let expected_length = 3;
3341         assert!(json_array.is_some() && json_array.unwrap().len() == expected_length);
3342     }
3343
3344     #[test]
3345     fn test_is_string(){
3346         let json_value = from_str("\"dog\"").unwrap();
3347         assert!(json_value.is_string());
3348     }
3349
3350     #[test]
3351     fn test_as_string(){
3352         let json_value = from_str("\"dog\"").unwrap();
3353         let json_str = json_value.as_string();
3354         let expected_str = "dog";
3355         assert_eq!(json_str, Some(expected_str));
3356     }
3357
3358     #[test]
3359     fn test_is_number(){
3360         let json_value = from_str("12").unwrap();
3361         assert!(json_value.is_number());
3362     }
3363
3364     #[test]
3365     fn test_is_i64(){
3366         let json_value = from_str("-12").unwrap();
3367         assert!(json_value.is_i64());
3368
3369         let json_value = from_str("12").unwrap();
3370         assert!(!json_value.is_i64());
3371
3372         let json_value = from_str("12.0").unwrap();
3373         assert!(!json_value.is_i64());
3374     }
3375
3376     #[test]
3377     fn test_is_u64(){
3378         let json_value = from_str("12").unwrap();
3379         assert!(json_value.is_u64());
3380
3381         let json_value = from_str("-12").unwrap();
3382         assert!(!json_value.is_u64());
3383
3384         let json_value = from_str("12.0").unwrap();
3385         assert!(!json_value.is_u64());
3386     }
3387
3388     #[test]
3389     fn test_is_f64(){
3390         let json_value = from_str("12").unwrap();
3391         assert!(!json_value.is_f64());
3392
3393         let json_value = from_str("-12").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         let json_value = from_str("-12.0").unwrap();
3400         assert!(json_value.is_f64());
3401     }
3402
3403     #[test]
3404     fn test_as_i64(){
3405         let json_value = from_str("-12").unwrap();
3406         let json_num = json_value.as_i64();
3407         assert_eq!(json_num, Some(-12));
3408     }
3409
3410     #[test]
3411     fn test_as_u64(){
3412         let json_value = from_str("12").unwrap();
3413         let json_num = json_value.as_u64();
3414         assert_eq!(json_num, Some(12));
3415     }
3416
3417     #[test]
3418     fn test_as_f64(){
3419         let json_value = from_str("12.0").unwrap();
3420         let json_num = json_value.as_f64();
3421         assert_eq!(json_num, Some(12f64));
3422     }
3423
3424     #[test]
3425     fn test_is_boolean(){
3426         let json_value = from_str("false").unwrap();
3427         assert!(json_value.is_boolean());
3428     }
3429
3430     #[test]
3431     fn test_as_boolean(){
3432         let json_value = from_str("false").unwrap();
3433         let json_bool = json_value.as_boolean();
3434         let expected_bool = false;
3435         assert!(json_bool.is_some() && json_bool.unwrap() == expected_bool);
3436     }
3437
3438     #[test]
3439     fn test_is_null(){
3440         let json_value = from_str("null").unwrap();
3441         assert!(json_value.is_null());
3442     }
3443
3444     #[test]
3445     fn test_as_null(){
3446         let json_value = from_str("null").unwrap();
3447         let json_null = json_value.as_null();
3448         let expected_null = ();
3449         assert!(json_null.is_some() && json_null.unwrap() == expected_null);
3450     }
3451
3452     #[test]
3453     fn test_encode_hashmap_with_numeric_key() {
3454         use std::str::from_utf8;
3455         use std::collections::HashMap;
3456         let mut hm: HashMap<usize, bool> = HashMap::new();
3457         hm.insert(1, true);
3458         let mut mem_buf = Vec::new();
3459         write!(&mut mem_buf, "{}", super::as_pretty_json(&hm)).unwrap();
3460         let json_str = from_utf8(&mem_buf[..]).unwrap();
3461         match from_str(json_str) {
3462             Err(_) => panic!("Unable to parse json_str: {:?}", json_str),
3463             _ => {} // it parsed and we are good to go
3464         }
3465     }
3466
3467     #[test]
3468     fn test_prettyencode_hashmap_with_numeric_key() {
3469         use std::str::from_utf8;
3470         use std::collections::HashMap;
3471         let mut hm: HashMap<usize, bool> = HashMap::new();
3472         hm.insert(1, true);
3473         let mut mem_buf = Vec::new();
3474         write!(&mut mem_buf, "{}", super::as_pretty_json(&hm)).unwrap();
3475         let json_str = from_utf8(&mem_buf[..]).unwrap();
3476         match from_str(json_str) {
3477             Err(_) => panic!("Unable to parse json_str: {:?}", json_str),
3478             _ => {} // it parsed and we are good to go
3479         }
3480     }
3481
3482     #[test]
3483     fn test_prettyencoder_indent_level_param() {
3484         use std::str::from_utf8;
3485         use std::collections::BTreeMap;
3486
3487         let mut tree = BTreeMap::new();
3488
3489         tree.insert("hello".to_string(), String("guten tag".to_string()));
3490         tree.insert("goodbye".to_string(), String("sayonara".to_string()));
3491
3492         let json = Array(
3493             // The following layout below should look a lot like
3494             // the pretty-printed JSON (indent * x)
3495             vec!
3496             ( // 0x
3497                 String("greetings".to_string()), // 1x
3498                 Object(tree), // 1x + 2x + 2x + 1x
3499             ) // 0x
3500             // End JSON array (7 lines)
3501         );
3502
3503         // Helper function for counting indents
3504         fn indents(source: &str) -> usize {
3505             let trimmed = source.trim_left_matches(' ');
3506             source.len() - trimmed.len()
3507         }
3508
3509         // Test up to 4 spaces of indents (more?)
3510         for i in 0..4 {
3511             let mut writer = Vec::new();
3512             write!(&mut writer, "{}",
3513                    super::as_pretty_json(&json).indent(i)).unwrap();
3514
3515             let printed = from_utf8(&writer[..]).unwrap();
3516
3517             // Check for indents at each line
3518             let lines: Vec<&str> = printed.lines().collect();
3519             assert_eq!(lines.len(), 7); // JSON should be 7 lines
3520
3521             assert_eq!(indents(lines[0]), 0 * i); // [
3522             assert_eq!(indents(lines[1]), 1 * i); //   "greetings",
3523             assert_eq!(indents(lines[2]), 1 * i); //   {
3524             assert_eq!(indents(lines[3]), 2 * i); //     "hello": "guten tag",
3525             assert_eq!(indents(lines[4]), 2 * i); //     "goodbye": "sayonara"
3526             assert_eq!(indents(lines[5]), 1 * i); //   },
3527             assert_eq!(indents(lines[6]), 0 * i); // ]
3528
3529             // Finally, test that the pretty-printed JSON is valid
3530             from_str(printed).ok().expect("Pretty-printed JSON is invalid!");
3531         }
3532     }
3533
3534     #[test]
3535     fn test_hashmap_with_enum_key() {
3536         use std::collections::HashMap;
3537         use json;
3538         #[derive(RustcEncodable, Eq, Hash, PartialEq, RustcDecodable, Debug)]
3539         enum Enum {
3540             Foo,
3541             #[allow(dead_code)]
3542             Bar,
3543         }
3544         let mut map = HashMap::new();
3545         map.insert(Enum::Foo, 0);
3546         let result = json::encode(&map).unwrap();
3547         assert_eq!(&result[..], r#"{"Foo":0}"#);
3548         let decoded: HashMap<Enum, _> = json::decode(&result).unwrap();
3549         assert_eq!(map, decoded);
3550     }
3551
3552     #[test]
3553     fn test_hashmap_with_numeric_key_can_handle_double_quote_delimited_key() {
3554         use std::collections::HashMap;
3555         use Decodable;
3556         let json_str = "{\"1\":true}";
3557         let json_obj = match from_str(json_str) {
3558             Err(_) => panic!("Unable to parse json_str: {:?}", json_str),
3559             Ok(o) => o
3560         };
3561         let mut decoder = Decoder::new(json_obj);
3562         let _hm: HashMap<usize, bool> = Decodable::decode(&mut decoder).unwrap();
3563     }
3564
3565     #[test]
3566     fn test_hashmap_with_numeric_key_will_error_with_string_keys() {
3567         use std::collections::HashMap;
3568         use Decodable;
3569         let json_str = "{\"a\":true}";
3570         let json_obj = match from_str(json_str) {
3571             Err(_) => panic!("Unable to parse json_str: {:?}", json_str),
3572             Ok(o) => o
3573         };
3574         let mut decoder = Decoder::new(json_obj);
3575         let result: Result<HashMap<usize, bool>, DecoderError> = Decodable::decode(&mut decoder);
3576         assert_eq!(result, Err(ExpectedError("Number".to_string(), "a".to_string())));
3577     }
3578
3579     fn assert_stream_equal(src: &str,
3580                            expected: Vec<(JsonEvent, Vec<StackElement>)>) {
3581         let mut parser = Parser::new(src.chars());
3582         let mut i = 0;
3583         loop {
3584             let evt = match parser.next() {
3585                 Some(e) => e,
3586                 None => { break; }
3587             };
3588             let (ref expected_evt, ref expected_stack) = expected[i];
3589             if !parser.stack().is_equal_to(expected_stack) {
3590                 panic!("Parser stack is not equal to {:?}", expected_stack);
3591             }
3592             assert_eq!(&evt, expected_evt);
3593             i+=1;
3594         }
3595     }
3596     #[test]
3597     fn test_streaming_parser() {
3598         assert_stream_equal(
3599             r#"{ "foo":"bar", "array" : [0, 1, 2, 3, 4, 5], "idents":[null,true,false]}"#,
3600             vec![
3601                 (ObjectStart,             vec![]),
3602                   (StringValue("bar".to_string()),   vec![StackElement::Key("foo")]),
3603                   (ArrayStart,            vec![StackElement::Key("array")]),
3604                     (U64Value(0),         vec![StackElement::Key("array"), StackElement::Index(0)]),
3605                     (U64Value(1),         vec![StackElement::Key("array"), StackElement::Index(1)]),
3606                     (U64Value(2),         vec![StackElement::Key("array"), StackElement::Index(2)]),
3607                     (U64Value(3),         vec![StackElement::Key("array"), StackElement::Index(3)]),
3608                     (U64Value(4),         vec![StackElement::Key("array"), StackElement::Index(4)]),
3609                     (U64Value(5),         vec![StackElement::Key("array"), StackElement::Index(5)]),
3610                   (ArrayEnd,              vec![StackElement::Key("array")]),
3611                   (ArrayStart,            vec![StackElement::Key("idents")]),
3612                     (NullValue,           vec![StackElement::Key("idents"),
3613                                                StackElement::Index(0)]),
3614                     (BooleanValue(true),  vec![StackElement::Key("idents"),
3615                                                StackElement::Index(1)]),
3616                     (BooleanValue(false), vec![StackElement::Key("idents"),
3617                                                StackElement::Index(2)]),
3618                   (ArrayEnd,              vec![StackElement::Key("idents")]),
3619                 (ObjectEnd,               vec![]),
3620             ]
3621         );
3622     }
3623     fn last_event(src: &str) -> JsonEvent {
3624         let mut parser = Parser::new(src.chars());
3625         let mut evt = NullValue;
3626         loop {
3627             evt = match parser.next() {
3628                 Some(e) => e,
3629                 None => return evt,
3630             }
3631         }
3632     }
3633
3634     #[test]
3635     fn test_read_object_streaming() {
3636         assert_eq!(last_event("{ "),      Error(SyntaxError(EOFWhileParsingObject, 1, 3)));
3637         assert_eq!(last_event("{1"),      Error(SyntaxError(KeyMustBeAString,      1, 2)));
3638         assert_eq!(last_event("{ \"a\""), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
3639         assert_eq!(last_event("{\"a\""),  Error(SyntaxError(EOFWhileParsingObject, 1, 5)));
3640         assert_eq!(last_event("{\"a\" "), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
3641
3642         assert_eq!(last_event("{\"a\" 1"),   Error(SyntaxError(ExpectedColon,         1, 6)));
3643         assert_eq!(last_event("{\"a\":"),    Error(SyntaxError(EOFWhileParsingValue,  1, 6)));
3644         assert_eq!(last_event("{\"a\":1"),   Error(SyntaxError(EOFWhileParsingObject, 1, 7)));
3645         assert_eq!(last_event("{\"a\":1 1"), Error(SyntaxError(InvalidSyntax,         1, 8)));
3646         assert_eq!(last_event("{\"a\":1,"),  Error(SyntaxError(EOFWhileParsingObject, 1, 8)));
3647         assert_eq!(last_event("{\"a\":1,}"), Error(SyntaxError(TrailingComma, 1, 8)));
3648
3649         assert_stream_equal(
3650             "{}",
3651             vec![(ObjectStart, vec![]), (ObjectEnd, vec![])]
3652         );
3653         assert_stream_equal(
3654             "{\"a\": 3}",
3655             vec![
3656                 (ObjectStart,        vec![]),
3657                   (U64Value(3),      vec![StackElement::Key("a")]),
3658                 (ObjectEnd,          vec![]),
3659             ]
3660         );
3661         assert_stream_equal(
3662             "{ \"a\": null, \"b\" : true }",
3663             vec![
3664                 (ObjectStart,           vec![]),
3665                   (NullValue,           vec![StackElement::Key("a")]),
3666                   (BooleanValue(true),  vec![StackElement::Key("b")]),
3667                 (ObjectEnd,             vec![]),
3668             ]
3669         );
3670         assert_stream_equal(
3671             "{\"a\" : 1.0 ,\"b\": [ true ]}",
3672             vec![
3673                 (ObjectStart,           vec![]),
3674                   (F64Value(1.0),       vec![StackElement::Key("a")]),
3675                   (ArrayStart,          vec![StackElement::Key("b")]),
3676                     (BooleanValue(true),vec![StackElement::Key("b"), StackElement::Index(0)]),
3677                   (ArrayEnd,            vec![StackElement::Key("b")]),
3678                 (ObjectEnd,             vec![]),
3679             ]
3680         );
3681         assert_stream_equal(
3682             r#"{
3683                 "a": 1.0,
3684                 "b": [
3685                     true,
3686                     "foo\nbar",
3687                     { "c": {"d": null} }
3688                 ]
3689             }"#,
3690             vec![
3691                 (ObjectStart,                   vec![]),
3692                   (F64Value(1.0),               vec![StackElement::Key("a")]),
3693                   (ArrayStart,                  vec![StackElement::Key("b")]),
3694                     (BooleanValue(true),        vec![StackElement::Key("b"),
3695                                                      StackElement::Index(0)]),
3696                     (StringValue("foo\nbar".to_string()),  vec![StackElement::Key("b"),
3697                                                                 StackElement::Index(1)]),
3698                     (ObjectStart,               vec![StackElement::Key("b"),
3699                                                      StackElement::Index(2)]),
3700                       (ObjectStart,             vec![StackElement::Key("b"),
3701                                                      StackElement::Index(2),
3702                                                      StackElement::Key("c")]),
3703                         (NullValue,             vec![StackElement::Key("b"),
3704                                                      StackElement::Index(2),
3705                                                      StackElement::Key("c"),
3706                                                      StackElement::Key("d")]),
3707                       (ObjectEnd,               vec![StackElement::Key("b"),
3708                                                      StackElement::Index(2),
3709                                                      StackElement::Key("c")]),
3710                     (ObjectEnd,                 vec![StackElement::Key("b"),
3711                                                      StackElement::Index(2)]),
3712                   (ArrayEnd,                    vec![StackElement::Key("b")]),
3713                 (ObjectEnd,                     vec![]),
3714             ]
3715         );
3716     }
3717     #[test]
3718     fn test_read_array_streaming() {
3719         assert_stream_equal(
3720             "[]",
3721             vec![
3722                 (ArrayStart, vec![]),
3723                 (ArrayEnd,   vec![]),
3724             ]
3725         );
3726         assert_stream_equal(
3727             "[ ]",
3728             vec![
3729                 (ArrayStart, vec![]),
3730                 (ArrayEnd,   vec![]),
3731             ]
3732         );
3733         assert_stream_equal(
3734             "[true]",
3735             vec![
3736                 (ArrayStart,             vec![]),
3737                     (BooleanValue(true), vec![StackElement::Index(0)]),
3738                 (ArrayEnd,               vec![]),
3739             ]
3740         );
3741         assert_stream_equal(
3742             "[ false ]",
3743             vec![
3744                 (ArrayStart,              vec![]),
3745                     (BooleanValue(false), vec![StackElement::Index(0)]),
3746                 (ArrayEnd,                vec![]),
3747             ]
3748         );
3749         assert_stream_equal(
3750             "[null]",
3751             vec![
3752                 (ArrayStart,    vec![]),
3753                     (NullValue, vec![StackElement::Index(0)]),
3754                 (ArrayEnd,      vec![]),
3755             ]
3756         );
3757         assert_stream_equal(
3758             "[3, 1]",
3759             vec![
3760                 (ArrayStart,      vec![]),
3761                     (U64Value(3), vec![StackElement::Index(0)]),
3762                     (U64Value(1), vec![StackElement::Index(1)]),
3763                 (ArrayEnd,        vec![]),
3764             ]
3765         );
3766         assert_stream_equal(
3767             "\n[3, 2]\n",
3768             vec![
3769                 (ArrayStart,      vec![]),
3770                     (U64Value(3), vec![StackElement::Index(0)]),
3771                     (U64Value(2), vec![StackElement::Index(1)]),
3772                 (ArrayEnd,        vec![]),
3773             ]
3774         );
3775         assert_stream_equal(
3776             "[2, [4, 1]]",
3777             vec![
3778                 (ArrayStart,           vec![]),
3779                     (U64Value(2),      vec![StackElement::Index(0)]),
3780                     (ArrayStart,       vec![StackElement::Index(1)]),
3781                         (U64Value(4),  vec![StackElement::Index(1), StackElement::Index(0)]),
3782                         (U64Value(1),  vec![StackElement::Index(1), StackElement::Index(1)]),
3783                     (ArrayEnd,         vec![StackElement::Index(1)]),
3784                 (ArrayEnd,             vec![]),
3785             ]
3786         );
3787
3788         assert_eq!(last_event("["), Error(SyntaxError(EOFWhileParsingValue, 1,  2)));
3789
3790         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
3791         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingArray, 1, 3)));
3792         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
3793         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
3794         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
3795
3796     }
3797     #[test]
3798     fn test_trailing_characters_streaming() {
3799         assert_eq!(last_event("nulla"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3800         assert_eq!(last_event("truea"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3801         assert_eq!(last_event("falsea"), Error(SyntaxError(TrailingCharacters, 1, 6)));
3802         assert_eq!(last_event("1a"),     Error(SyntaxError(TrailingCharacters, 1, 2)));
3803         assert_eq!(last_event("[]a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3804         assert_eq!(last_event("{}a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3805     }
3806     #[test]
3807     fn test_read_identifiers_streaming() {
3808         assert_eq!(Parser::new("null".chars()).next(), Some(NullValue));
3809         assert_eq!(Parser::new("true".chars()).next(), Some(BooleanValue(true)));
3810         assert_eq!(Parser::new("false".chars()).next(), Some(BooleanValue(false)));
3811
3812         assert_eq!(last_event("n"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3813         assert_eq!(last_event("nul"),  Error(SyntaxError(InvalidSyntax, 1, 4)));
3814         assert_eq!(last_event("t"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3815         assert_eq!(last_event("truz"), Error(SyntaxError(InvalidSyntax, 1, 4)));
3816         assert_eq!(last_event("f"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3817         assert_eq!(last_event("faz"),  Error(SyntaxError(InvalidSyntax, 1, 3)));
3818     }
3819
3820     #[test]
3821     fn test_stack() {
3822         let mut stack = Stack::new();
3823
3824         assert!(stack.is_empty());
3825         assert!(stack.is_empty());
3826         assert!(!stack.last_is_index());
3827
3828         stack.push_index(0);
3829         stack.bump_index();
3830
3831         assert!(stack.len() == 1);
3832         assert!(stack.is_equal_to(&[StackElement::Index(1)]));
3833         assert!(stack.starts_with(&[StackElement::Index(1)]));
3834         assert!(stack.ends_with(&[StackElement::Index(1)]));
3835         assert!(stack.last_is_index());
3836         assert!(stack.get(0) == StackElement::Index(1));
3837
3838         stack.push_key("foo".to_string());
3839
3840         assert!(stack.len() == 2);
3841         assert!(stack.is_equal_to(&[StackElement::Index(1), StackElement::Key("foo")]));
3842         assert!(stack.starts_with(&[StackElement::Index(1), StackElement::Key("foo")]));
3843         assert!(stack.starts_with(&[StackElement::Index(1)]));
3844         assert!(stack.ends_with(&[StackElement::Index(1), StackElement::Key("foo")]));
3845         assert!(stack.ends_with(&[StackElement::Key("foo")]));
3846         assert!(!stack.last_is_index());
3847         assert!(stack.get(0) == StackElement::Index(1));
3848         assert!(stack.get(1) == StackElement::Key("foo"));
3849
3850         stack.push_key("bar".to_string());
3851
3852         assert!(stack.len() == 3);
3853         assert!(stack.is_equal_to(&[StackElement::Index(1),
3854                                     StackElement::Key("foo"),
3855                                     StackElement::Key("bar")]));
3856         assert!(stack.starts_with(&[StackElement::Index(1)]));
3857         assert!(stack.starts_with(&[StackElement::Index(1), StackElement::Key("foo")]));
3858         assert!(stack.starts_with(&[StackElement::Index(1),
3859                                     StackElement::Key("foo"),
3860                                     StackElement::Key("bar")]));
3861         assert!(stack.ends_with(&[StackElement::Key("bar")]));
3862         assert!(stack.ends_with(&[StackElement::Key("foo"), StackElement::Key("bar")]));
3863         assert!(stack.ends_with(&[StackElement::Index(1),
3864                                   StackElement::Key("foo"),
3865                                   StackElement::Key("bar")]));
3866         assert!(!stack.last_is_index());
3867         assert!(stack.get(0) == StackElement::Index(1));
3868         assert!(stack.get(1) == StackElement::Key("foo"));
3869         assert!(stack.get(2) == StackElement::Key("bar"));
3870
3871         stack.pop();
3872
3873         assert!(stack.len() == 2);
3874         assert!(stack.is_equal_to(&[StackElement::Index(1), StackElement::Key("foo")]));
3875         assert!(stack.starts_with(&[StackElement::Index(1), StackElement::Key("foo")]));
3876         assert!(stack.starts_with(&[StackElement::Index(1)]));
3877         assert!(stack.ends_with(&[StackElement::Index(1), StackElement::Key("foo")]));
3878         assert!(stack.ends_with(&[StackElement::Key("foo")]));
3879         assert!(!stack.last_is_index());
3880         assert!(stack.get(0) == StackElement::Index(1));
3881         assert!(stack.get(1) == StackElement::Key("foo"));
3882     }
3883
3884     #[test]
3885     fn test_to_json() {
3886         use std::collections::{HashMap,BTreeMap};
3887         use super::ToJson;
3888
3889         let array2 = Array(vec![U64(1), U64(2)]);
3890         let array3 = Array(vec![U64(1), U64(2), U64(3)]);
3891         let object = {
3892             let mut tree_map = BTreeMap::new();
3893             tree_map.insert("a".to_string(), U64(1));
3894             tree_map.insert("b".to_string(), U64(2));
3895             Object(tree_map)
3896         };
3897
3898         assert_eq!(array2.to_json(), array2);
3899         assert_eq!(object.to_json(), object);
3900         assert_eq!(3_isize.to_json(), I64(3));
3901         assert_eq!(4_i8.to_json(), I64(4));
3902         assert_eq!(5_i16.to_json(), I64(5));
3903         assert_eq!(6_i32.to_json(), I64(6));
3904         assert_eq!(7_i64.to_json(), I64(7));
3905         assert_eq!(8_usize.to_json(), U64(8));
3906         assert_eq!(9_u8.to_json(), U64(9));
3907         assert_eq!(10_u16.to_json(), U64(10));
3908         assert_eq!(11_u32.to_json(), U64(11));
3909         assert_eq!(12_u64.to_json(), U64(12));
3910         assert_eq!(13.0_f32.to_json(), F64(13.0_f64));
3911         assert_eq!(14.0_f64.to_json(), F64(14.0_f64));
3912         assert_eq!(().to_json(), Null);
3913         assert_eq!(f32::INFINITY.to_json(), Null);
3914         assert_eq!(f64::NAN.to_json(), Null);
3915         assert_eq!(true.to_json(), Boolean(true));
3916         assert_eq!(false.to_json(), Boolean(false));
3917         assert_eq!("abc".to_json(), String("abc".to_string()));
3918         assert_eq!("abc".to_string().to_json(), String("abc".to_string()));
3919         assert_eq!((1_usize, 2_usize).to_json(), array2);
3920         assert_eq!((1_usize, 2_usize, 3_usize).to_json(), array3);
3921         assert_eq!([1_usize, 2_usize].to_json(), array2);
3922         assert_eq!((&[1_usize, 2_usize, 3_usize]).to_json(), array3);
3923         assert_eq!((vec![1_usize, 2_usize]).to_json(), array2);
3924         assert_eq!(vec![1_usize, 2_usize, 3_usize].to_json(), array3);
3925         let mut tree_map = BTreeMap::new();
3926         tree_map.insert("a".to_string(), 1 as usize);
3927         tree_map.insert("b".to_string(), 2);
3928         assert_eq!(tree_map.to_json(), object);
3929         let mut hash_map = HashMap::new();
3930         hash_map.insert("a".to_string(), 1 as usize);
3931         hash_map.insert("b".to_string(), 2);
3932         assert_eq!(hash_map.to_json(), object);
3933         assert_eq!(Some(15).to_json(), I64(15));
3934         assert_eq!(Some(15 as usize).to_json(), U64(15));
3935         assert_eq!(None::<isize>.to_json(), Null);
3936     }
3937
3938     #[test]
3939     fn test_encode_hashmap_with_arbitrary_key() {
3940         use std::collections::HashMap;
3941         #[derive(PartialEq, Eq, Hash, RustcEncodable)]
3942         struct ArbitraryType(usize);
3943         let mut hm: HashMap<ArbitraryType, bool> = HashMap::new();
3944         hm.insert(ArbitraryType(1), true);
3945         let mut mem_buf = string::String::new();
3946         let mut encoder = Encoder::new(&mut mem_buf);
3947         let result = hm.encode(&mut encoder);
3948         match result.unwrap_err() {
3949             EncoderError::BadHashmapKey => (),
3950             _ => panic!("expected bad hash map key")
3951         }
3952     }
3953
3954     #[bench]
3955     fn bench_streaming_small(b: &mut Bencher) {
3956         b.iter( || {
3957             let mut parser = Parser::new(
3958                 r#"{
3959                     "a": 1.0,
3960                     "b": [
3961                         true,
3962                         "foo\nbar",
3963                         { "c": {"d": null} }
3964                     ]
3965                 }"#.chars()
3966             );
3967             loop {
3968                 match parser.next() {
3969                     None => return,
3970                     _ => {}
3971                 }
3972             }
3973         });
3974     }
3975     #[bench]
3976     fn bench_small(b: &mut Bencher) {
3977         b.iter( || {
3978             let _ = from_str(r#"{
3979                 "a": 1.0,
3980                 "b": [
3981                     true,
3982                     "foo\nbar",
3983                     { "c": {"d": null} }
3984                 ]
3985             }"#);
3986         });
3987     }
3988
3989     fn big_json() -> string::String {
3990         let mut src = "[\n".to_string();
3991         for _ in 0..500 {
3992             src.push_str(r#"{ "a": true, "b": null, "c":3.1415, "d": "Hello world", "e": \
3993                             [1,2,3]},"#);
3994         }
3995         src.push_str("{}]");
3996         return src;
3997     }
3998
3999     #[bench]
4000     fn bench_streaming_large(b: &mut Bencher) {
4001         let src = big_json();
4002         b.iter( || {
4003             let mut parser = Parser::new(src.chars());
4004             loop {
4005                 match parser.next() {
4006                     None => return,
4007                     _ => {}
4008                 }
4009             }
4010         });
4011     }
4012     #[bench]
4013     fn bench_large(b: &mut Bencher) {
4014         let src = big_json();
4015         b.iter( || { let _ = from_str(&src); });
4016     }
4017 }