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