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