src/libserialize/json.rs

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