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