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