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