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