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