src/libserialize/json.rs

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