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 => return Err(MissingFieldError(name.to_string())),
2132             Some(json) => {
2133                 self.stack.push(json);
2134                 try!(f(self))
2135             }
2136         };
2137         self.stack.push(Object(obj));
2138         Ok(value)
2139     }
2140
2141     fn read_tuple<T>(&mut self, f: |&mut Decoder, uint| -> DecodeResult<T>) -> DecodeResult<T> {
2142         debug!("read_tuple()");
2143         self.read_seq(f)
2144     }
2145
2146     fn read_tuple_arg<T>(&mut self,
2147                          idx: uint,
2148                          f: |&mut Decoder| -> DecodeResult<T>) -> DecodeResult<T> {
2149         debug!("read_tuple_arg(idx={})", idx);
2150         self.read_seq_elt(idx, f)
2151     }
2152
2153     fn read_tuple_struct<T>(&mut self,
2154                             name: &str,
2155                             f: |&mut Decoder, uint| -> DecodeResult<T>)
2156                             -> DecodeResult<T> {
2157         debug!("read_tuple_struct(name={})", name);
2158         self.read_tuple(f)
2159     }
2160
2161     fn read_tuple_struct_arg<T>(&mut self,
2162                                 idx: uint,
2163                                 f: |&mut Decoder| -> DecodeResult<T>)
2164                                 -> DecodeResult<T> {
2165         debug!("read_tuple_struct_arg(idx={})", idx);
2166         self.read_tuple_arg(idx, f)
2167     }
2168
2169     fn read_option<T>(&mut self, f: |&mut Decoder, bool| -> DecodeResult<T>) -> DecodeResult<T> {
2170         match self.pop() {
2171             Null => f(self, false),
2172             value => { self.stack.push(value); f(self, true) }
2173         }
2174     }
2175
2176     fn read_seq<T>(&mut self, f: |&mut Decoder, uint| -> DecodeResult<T>) -> DecodeResult<T> {
2177         debug!("read_seq()");
2178         let list = try!(expect!(self.pop(), List));
2179         let len = list.len();
2180         for v in list.move_iter().rev() {
2181             self.stack.push(v);
2182         }
2183         f(self, len)
2184     }
2185
2186     fn read_seq_elt<T>(&mut self,
2187                        idx: uint,
2188                        f: |&mut Decoder| -> DecodeResult<T>) -> DecodeResult<T> {
2189         debug!("read_seq_elt(idx={})", idx);
2190         f(self)
2191     }
2192
2193     fn read_map<T>(&mut self, f: |&mut Decoder, uint| -> DecodeResult<T>) -> DecodeResult<T> {
2194         debug!("read_map()");
2195         let obj = try!(expect!(self.pop(), Object));
2196         let len = obj.len();
2197         for (key, value) in obj.move_iter() {
2198             self.stack.push(value);
2199             self.stack.push(String(key));
2200         }
2201         f(self, len)
2202     }
2203
2204     fn read_map_elt_key<T>(&mut self, idx: uint, f: |&mut Decoder| -> DecodeResult<T>)
2205                            -> DecodeResult<T> {
2206         debug!("read_map_elt_key(idx={})", idx);
2207         f(self)
2208     }
2209
2210     fn read_map_elt_val<T>(&mut self, idx: uint, f: |&mut Decoder| -> DecodeResult<T>)
2211                            -> DecodeResult<T> {
2212         debug!("read_map_elt_val(idx={})", idx);
2213         f(self)
2214     }
2215
2216     fn error(&mut self, err: &str) -> DecoderError {
2217         ApplicationError(err.to_string())
2218     }
2219 }
2220
2221 /// A trait for converting values to JSON
2222 pub trait ToJson {
2223     /// Converts the value of `self` to an instance of JSON
2224     fn to_json(&self) -> Json;
2225 }
2226
2227 macro_rules! to_json_impl_i64(
2228     ($($t:ty), +) => (
2229         $(impl ToJson for $t {
2230             fn to_json(&self) -> Json { I64(*self as i64) }
2231         })+
2232     )
2233 )
2234
2235 to_json_impl_i64!(int, i8, i16, i32, i64)
2236
2237 macro_rules! to_json_impl_u64(
2238     ($($t:ty), +) => (
2239         $(impl ToJson for $t {
2240             fn to_json(&self) -> Json { U64(*self as u64) }
2241         })+
2242     )
2243 )
2244
2245 to_json_impl_u64!(uint, u8, u16, u32, u64)
2246
2247 impl ToJson for Json {
2248     fn to_json(&self) -> Json { self.clone() }
2249 }
2250
2251 impl ToJson for f32 {
2252     fn to_json(&self) -> Json { (*self as f64).to_json() }
2253 }
2254
2255 impl ToJson for f64 {
2256     fn to_json(&self) -> Json {
2257         match self.classify() {
2258             FPNaN | FPInfinite => Null,
2259             _                  => F64(*self)
2260         }
2261     }
2262 }
2263
2264 impl ToJson for () {
2265     fn to_json(&self) -> Json { Null }
2266 }
2267
2268 impl ToJson for bool {
2269     fn to_json(&self) -> Json { Boolean(*self) }
2270 }
2271
2272 impl ToJson for String {
2273     fn to_json(&self) -> Json { String((*self).clone()) }
2274 }
2275
2276 macro_rules! tuple_impl {
2277     // use variables to indicate the arity of the tuple
2278     ($($tyvar:ident),* ) => {
2279         // the trailing commas are for the 1 tuple
2280         impl<
2281             $( $tyvar : ToJson ),*
2282             > ToJson for ( $( $tyvar ),* , ) {
2283
2284             #[inline]
2285             #[allow(non_snake_case)]
2286             fn to_json(&self) -> Json {
2287                 match *self {
2288                     ($(ref $tyvar),*,) => List(vec![$($tyvar.to_json()),*])
2289                 }
2290             }
2291         }
2292     }
2293 }
2294
2295 tuple_impl!{A}
2296 tuple_impl!{A, B}
2297 tuple_impl!{A, B, C}
2298 tuple_impl!{A, B, C, D}
2299 tuple_impl!{A, B, C, D, E}
2300 tuple_impl!{A, B, C, D, E, F}
2301 tuple_impl!{A, B, C, D, E, F, G}
2302 tuple_impl!{A, B, C, D, E, F, G, H}
2303 tuple_impl!{A, B, C, D, E, F, G, H, I}
2304 tuple_impl!{A, B, C, D, E, F, G, H, I, J}
2305 tuple_impl!{A, B, C, D, E, F, G, H, I, J, K}
2306 tuple_impl!{A, B, C, D, E, F, G, H, I, J, K, L}
2307
2308 impl<'a, A: ToJson> ToJson for &'a [A] {
2309     fn to_json(&self) -> Json { List(self.iter().map(|elt| elt.to_json()).collect()) }
2310 }
2311
2312 impl<A: ToJson> ToJson for Vec<A> {
2313     fn to_json(&self) -> Json { List(self.iter().map(|elt| elt.to_json()).collect()) }
2314 }
2315
2316 impl<A: ToJson> ToJson for TreeMap<String, A> {
2317     fn to_json(&self) -> Json {
2318         let mut d = TreeMap::new();
2319         for (key, value) in self.iter() {
2320             d.insert((*key).clone(), value.to_json());
2321         }
2322         Object(d)
2323     }
2324 }
2325
2326 impl<A: ToJson> ToJson for HashMap<String, A> {
2327     fn to_json(&self) -> Json {
2328         let mut d = TreeMap::new();
2329         for (key, value) in self.iter() {
2330             d.insert((*key).clone(), value.to_json());
2331         }
2332         Object(d)
2333     }
2334 }
2335
2336 impl<A:ToJson> ToJson for Option<A> {
2337     fn to_json(&self) -> Json {
2338         match *self {
2339             None => Null,
2340             Some(ref value) => value.to_json()
2341         }
2342     }
2343 }
2344
2345 impl fmt::Show for Json {
2346     /// Encodes a json value into a string
2347     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2348         self.to_writer(f).map_err(|_| fmt::WriteError)
2349     }
2350 }
2351
2352 impl std::from_str::FromStr for Json {
2353     fn from_str(s: &str) -> Option<Json> {
2354         from_str(s).ok()
2355     }
2356 }
2357
2358 #[cfg(test)]
2359 mod tests {
2360     extern crate test;
2361     use self::test::Bencher;
2362     use {Encodable, Decodable};
2363     use super::{Encoder, Decoder, Error, Boolean, I64, U64, F64, List, String, Null,
2364                 PrettyEncoder, Object, Json, from_str, ParseError, ExpectedError,
2365                 MissingFieldError, UnknownVariantError, DecodeResult, DecoderError,
2366                 JsonEvent, Parser, StackElement,
2367                 ObjectStart, ObjectEnd, ListStart, ListEnd, BooleanValue, U64Value,
2368                 F64Value, StringValue, NullValue, SyntaxError, Key, Index, Stack,
2369                 InvalidSyntax, InvalidNumber, EOFWhileParsingObject, EOFWhileParsingList,
2370                 EOFWhileParsingValue, EOFWhileParsingString, KeyMustBeAString, ExpectedColon,
2371                 TrailingCharacters};
2372     use std::{i64, u64, f32, f64, io};
2373     use std::collections::TreeMap;
2374
2375     #[deriving(PartialEq, Encodable, Decodable, Show)]
2376     enum Animal {
2377         Dog,
2378         Frog(String, int)
2379     }
2380
2381     #[deriving(PartialEq, Encodable, Decodable, Show)]
2382     struct Inner {
2383         a: (),
2384         b: uint,
2385         c: Vec<String>,
2386     }
2387
2388     #[deriving(PartialEq, Encodable, Decodable, Show)]
2389     struct Outer {
2390         inner: Vec<Inner>,
2391     }
2392
2393     fn mk_object(items: &[(String, Json)]) -> Json {
2394         let mut d = TreeMap::new();
2395
2396         for item in items.iter() {
2397             match *item {
2398                 (ref key, ref value) => { d.insert((*key).clone(), (*value).clone()); },
2399             }
2400         };
2401
2402         Object(d)
2403     }
2404
2405     #[test]
2406     fn test_from_str_trait() {
2407         let s = "null";
2408         assert!(::std::from_str::from_str::<Json>(s).unwrap() == from_str(s).unwrap());
2409     }
2410
2411     #[test]
2412     fn test_write_null() {
2413         assert_eq!(Null.to_string().into_string(), "null".to_string());
2414         assert_eq!(Null.to_pretty_str().into_string(), "null".to_string());
2415     }
2416
2417     #[test]
2418     fn test_write_i64() {
2419         assert_eq!(U64(0).to_string().into_string(), "0".to_string());
2420         assert_eq!(U64(0).to_pretty_str().into_string(), "0".to_string());
2421
2422         assert_eq!(U64(1234).to_string().into_string(), "1234".to_string());
2423         assert_eq!(U64(1234).to_pretty_str().into_string(), "1234".to_string());
2424
2425         assert_eq!(I64(-5678).to_string().into_string(), "-5678".to_string());
2426         assert_eq!(I64(-5678).to_pretty_str().into_string(), "-5678".to_string());
2427     }
2428
2429     #[test]
2430     fn test_write_f64() {
2431         assert_eq!(F64(3.0).to_string().into_string(), "3".to_string());
2432         assert_eq!(F64(3.0).to_pretty_str().into_string(), "3".to_string());
2433
2434         assert_eq!(F64(3.1).to_string().into_string(), "3.1".to_string());
2435         assert_eq!(F64(3.1).to_pretty_str().into_string(), "3.1".to_string());
2436
2437         assert_eq!(F64(-1.5).to_string().into_string(), "-1.5".to_string());
2438         assert_eq!(F64(-1.5).to_pretty_str().into_string(), "-1.5".to_string());
2439
2440         assert_eq!(F64(0.5).to_string().into_string(), "0.5".to_string());
2441         assert_eq!(F64(0.5).to_pretty_str().into_string(), "0.5".to_string());
2442
2443         assert_eq!(F64(f64::NAN).to_string().into_string(), "null".to_string());
2444         assert_eq!(F64(f64::NAN).to_pretty_str().into_string(), "null".to_string());
2445
2446         assert_eq!(F64(f64::INFINITY).to_string().into_string(), "null".to_string());
2447         assert_eq!(F64(f64::INFINITY).to_pretty_str().into_string(), "null".to_string());
2448
2449         assert_eq!(F64(f64::NEG_INFINITY).to_string().into_string(), "null".to_string());
2450         assert_eq!(F64(f64::NEG_INFINITY).to_pretty_str().into_string(), "null".to_string());
2451     }
2452
2453     #[test]
2454     fn test_write_str() {
2455         assert_eq!(String("".to_string()).to_string().into_string(), "\"\"".to_string());
2456         assert_eq!(String("".to_string()).to_pretty_str().into_string(), "\"\"".to_string());
2457
2458         assert_eq!(String("foo".to_string()).to_string().into_string(), "\"foo\"".to_string());
2459         assert_eq!(String("foo".to_string()).to_pretty_str().into_string(), "\"foo\"".to_string());
2460     }
2461
2462     #[test]
2463     fn test_write_bool() {
2464         assert_eq!(Boolean(true).to_string().into_string(), "true".to_string());
2465         assert_eq!(Boolean(true).to_pretty_str().into_string(), "true".to_string());
2466
2467         assert_eq!(Boolean(false).to_string().into_string(), "false".to_string());
2468         assert_eq!(Boolean(false).to_pretty_str().into_string(), "false".to_string());
2469     }
2470
2471     #[test]
2472     fn test_write_list() {
2473         assert_eq!(List(vec![]).to_string().into_string(), "[]".to_string());
2474         assert_eq!(List(vec![]).to_pretty_str().into_string(), "[]".to_string());
2475
2476         assert_eq!(List(vec![Boolean(true)]).to_string().into_string(), "[true]".to_string());
2477         assert_eq!(
2478             List(vec![Boolean(true)]).to_pretty_str().into_string(),
2479             "\
2480             [\n  \
2481                 true\n\
2482             ]".to_string()
2483         );
2484
2485         let long_test_list = List(vec![
2486             Boolean(false),
2487             Null,
2488             List(vec![String("foo\nbar".to_string()), F64(3.5)])]);
2489
2490         assert_eq!(long_test_list.to_string().into_string(),
2491             "[false,null,[\"foo\\nbar\",3.5]]".to_string());
2492         assert_eq!(
2493             long_test_list.to_pretty_str().into_string(),
2494             "\
2495             [\n  \
2496                 false,\n  \
2497                 null,\n  \
2498                 [\n    \
2499                     \"foo\\nbar\",\n    \
2500                     3.5\n  \
2501                 ]\n\
2502             ]".to_string()
2503         );
2504     }
2505
2506     #[test]
2507     fn test_write_object() {
2508         assert_eq!(mk_object([]).to_string().into_string(), "{}".to_string());
2509         assert_eq!(mk_object([]).to_pretty_str().into_string(), "{}".to_string());
2510
2511         assert_eq!(
2512             mk_object([
2513                 ("a".to_string(), Boolean(true))
2514             ]).to_string().into_string(),
2515             "{\"a\":true}".to_string()
2516         );
2517         assert_eq!(
2518             mk_object([("a".to_string(), Boolean(true))]).to_pretty_str(),
2519             "\
2520             {\n  \
2521                 \"a\": true\n\
2522             }".to_string()
2523         );
2524
2525         let complex_obj = mk_object([
2526                 ("b".to_string(), List(vec![
2527                     mk_object([("c".to_string(), String("\x0c\r".to_string()))]),
2528                     mk_object([("d".to_string(), String("".to_string()))])
2529                 ]))
2530             ]);
2531
2532         assert_eq!(
2533             complex_obj.to_string().into_string(),
2534             "{\
2535                 \"b\":[\
2536                     {\"c\":\"\\f\\r\"},\
2537                     {\"d\":\"\"}\
2538                 ]\
2539             }".to_string()
2540         );
2541         assert_eq!(
2542             complex_obj.to_pretty_str().into_string(),
2543             "\
2544             {\n  \
2545                 \"b\": [\n    \
2546                     {\n      \
2547                         \"c\": \"\\f\\r\"\n    \
2548                     },\n    \
2549                     {\n      \
2550                         \"d\": \"\"\n    \
2551                     }\n  \
2552                 ]\n\
2553             }".to_string()
2554         );
2555
2556         let a = mk_object([
2557             ("a".to_string(), Boolean(true)),
2558             ("b".to_string(), List(vec![
2559                 mk_object([("c".to_string(), String("\x0c\r".to_string()))]),
2560                 mk_object([("d".to_string(), String("".to_string()))])
2561             ]))
2562         ]);
2563
2564         // We can't compare the strings directly because the object fields be
2565         // printed in a different order.
2566         assert_eq!(a.clone(), from_str(a.to_string().as_slice()).unwrap());
2567         assert_eq!(a.clone(),
2568                    from_str(a.to_pretty_str().as_slice()).unwrap());
2569     }
2570
2571     fn with_str_writer(f: |&mut io::Writer|) -> String {
2572         use std::io::MemWriter;
2573         use std::str;
2574
2575         let mut m = MemWriter::new();
2576         f(&mut m as &mut io::Writer);
2577         str::from_utf8(m.unwrap().as_slice()).unwrap().to_string()
2578     }
2579
2580     #[test]
2581     fn test_write_enum() {
2582         let animal = Dog;
2583         assert_eq!(
2584             with_str_writer(|writer| {
2585                 let mut encoder = Encoder::new(writer);
2586                 animal.encode(&mut encoder).unwrap();
2587             }),
2588             "\"Dog\"".to_string()
2589         );
2590         assert_eq!(
2591             with_str_writer(|writer| {
2592                 let mut encoder = PrettyEncoder::new(writer);
2593                 animal.encode(&mut encoder).unwrap();
2594             }),
2595             "\"Dog\"".to_string()
2596         );
2597
2598         let animal = Frog("Henry".to_string(), 349);
2599         assert_eq!(
2600             with_str_writer(|writer| {
2601                 let mut encoder = Encoder::new(writer);
2602                 animal.encode(&mut encoder).unwrap();
2603             }),
2604             "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}".to_string()
2605         );
2606         assert_eq!(
2607             with_str_writer(|writer| {
2608                 let mut encoder = PrettyEncoder::new(writer);
2609                 animal.encode(&mut encoder).unwrap();
2610             }),
2611             "\
2612             [\n  \
2613                 \"Frog\",\n  \
2614                 \"Henry\",\n  \
2615                 349\n\
2616             ]".to_string()
2617         );
2618     }
2619
2620     #[test]
2621     fn test_write_some() {
2622         let value = Some("jodhpurs".to_string());
2623         let s = with_str_writer(|writer| {
2624             let mut encoder = Encoder::new(writer);
2625             value.encode(&mut encoder).unwrap();
2626         });
2627         assert_eq!(s, "\"jodhpurs\"".to_string());
2628
2629         let value = Some("jodhpurs".to_string());
2630         let s = with_str_writer(|writer| {
2631             let mut encoder = PrettyEncoder::new(writer);
2632             value.encode(&mut encoder).unwrap();
2633         });
2634         assert_eq!(s, "\"jodhpurs\"".to_string());
2635     }
2636
2637     #[test]
2638     fn test_write_none() {
2639         let value: Option<String> = None;
2640         let s = with_str_writer(|writer| {
2641             let mut encoder = Encoder::new(writer);
2642             value.encode(&mut encoder).unwrap();
2643         });
2644         assert_eq!(s, "null".to_string());
2645
2646         let s = with_str_writer(|writer| {
2647             let mut encoder = Encoder::new(writer);
2648             value.encode(&mut encoder).unwrap();
2649         });
2650         assert_eq!(s, "null".to_string());
2651     }
2652
2653     #[test]
2654     fn test_trailing_characters() {
2655         assert_eq!(from_str("nulla"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2656         assert_eq!(from_str("truea"),  Err(SyntaxError(TrailingCharacters, 1, 5)));
2657         assert_eq!(from_str("falsea"), Err(SyntaxError(TrailingCharacters, 1, 6)));
2658         assert_eq!(from_str("1a"),     Err(SyntaxError(TrailingCharacters, 1, 2)));
2659         assert_eq!(from_str("[]a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2660         assert_eq!(from_str("{}a"),    Err(SyntaxError(TrailingCharacters, 1, 3)));
2661     }
2662
2663     #[test]
2664     fn test_read_identifiers() {
2665         assert_eq!(from_str("n"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2666         assert_eq!(from_str("nul"),  Err(SyntaxError(InvalidSyntax, 1, 4)));
2667         assert_eq!(from_str("t"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2668         assert_eq!(from_str("truz"), Err(SyntaxError(InvalidSyntax, 1, 4)));
2669         assert_eq!(from_str("f"),    Err(SyntaxError(InvalidSyntax, 1, 2)));
2670         assert_eq!(from_str("faz"),  Err(SyntaxError(InvalidSyntax, 1, 3)));
2671
2672         assert_eq!(from_str("null"), Ok(Null));
2673         assert_eq!(from_str("true"), Ok(Boolean(true)));
2674         assert_eq!(from_str("false"), Ok(Boolean(false)));
2675         assert_eq!(from_str(" null "), Ok(Null));
2676         assert_eq!(from_str(" true "), Ok(Boolean(true)));
2677         assert_eq!(from_str(" false "), Ok(Boolean(false)));
2678     }
2679
2680     #[test]
2681     fn test_decode_identifiers() {
2682         let v: () = super::decode("null").unwrap();
2683         assert_eq!(v, ());
2684
2685         let v: bool = super::decode("true").unwrap();
2686         assert_eq!(v, true);
2687
2688         let v: bool = super::decode("false").unwrap();
2689         assert_eq!(v, false);
2690     }
2691
2692     #[test]
2693     fn test_read_number() {
2694         assert_eq!(from_str("+"),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2695         assert_eq!(from_str("."),   Err(SyntaxError(InvalidSyntax, 1, 1)));
2696         assert_eq!(from_str("NaN"), Err(SyntaxError(InvalidSyntax, 1, 1)));
2697         assert_eq!(from_str("-"),   Err(SyntaxError(InvalidNumber, 1, 2)));
2698         assert_eq!(from_str("00"),  Err(SyntaxError(InvalidNumber, 1, 2)));
2699         assert_eq!(from_str("1."),  Err(SyntaxError(InvalidNumber, 1, 3)));
2700         assert_eq!(from_str("1e"),  Err(SyntaxError(InvalidNumber, 1, 3)));
2701         assert_eq!(from_str("1e+"), Err(SyntaxError(InvalidNumber, 1, 4)));
2702
2703         assert_eq!(from_str("18446744073709551616"), Err(SyntaxError(InvalidNumber, 1, 20)));
2704         assert_eq!(from_str("-9223372036854775809"), Err(SyntaxError(InvalidNumber, 1, 21)));
2705
2706         assert_eq!(from_str("3"), Ok(U64(3)));
2707         assert_eq!(from_str("3.1"), Ok(F64(3.1)));
2708         assert_eq!(from_str("-1.2"), Ok(F64(-1.2)));
2709         assert_eq!(from_str("0.4"), Ok(F64(0.4)));
2710         assert_eq!(from_str("0.4e5"), Ok(F64(0.4e5)));
2711         assert_eq!(from_str("0.4e+15"), Ok(F64(0.4e15)));
2712         assert_eq!(from_str("0.4e-01"), Ok(F64(0.4e-01)));
2713         assert_eq!(from_str(" 3 "), Ok(U64(3)));
2714
2715         assert_eq!(from_str("-9223372036854775808"), Ok(I64(i64::MIN)));
2716         assert_eq!(from_str("9223372036854775807"), Ok(U64(i64::MAX as u64)));
2717         assert_eq!(from_str("18446744073709551615"), Ok(U64(u64::MAX)));
2718     }
2719
2720     #[test]
2721     fn test_decode_numbers() {
2722         let v: f64 = super::decode("3").unwrap();
2723         assert_eq!(v, 3.0);
2724
2725         let v: f64 = super::decode("3.1").unwrap();
2726         assert_eq!(v, 3.1);
2727
2728         let v: f64 = super::decode("-1.2").unwrap();
2729         assert_eq!(v, -1.2);
2730
2731         let v: f64 = super::decode("0.4").unwrap();
2732         assert_eq!(v, 0.4);
2733
2734         let v: f64 = super::decode("0.4e5").unwrap();
2735         assert_eq!(v, 0.4e5);
2736
2737         let v: f64 = super::decode("0.4e15").unwrap();
2738         assert_eq!(v, 0.4e15);
2739
2740         let v: f64 = super::decode("0.4e-01").unwrap();
2741         assert_eq!(v, 0.4e-01);
2742
2743         let v: u64 = super::decode("0").unwrap();
2744         assert_eq!(v, 0);
2745
2746         let v: u64 = super::decode("18446744073709551615").unwrap();
2747         assert_eq!(v, u64::MAX);
2748
2749         let v: i64 = super::decode("-9223372036854775808").unwrap();
2750         assert_eq!(v, i64::MIN);
2751
2752         let v: i64 = super::decode("9223372036854775807").unwrap();
2753         assert_eq!(v, i64::MAX);
2754     }
2755
2756     #[test]
2757     fn test_read_str() {
2758         assert_eq!(from_str("\""),    Err(SyntaxError(EOFWhileParsingString, 1, 2)));
2759         assert_eq!(from_str("\"lol"), Err(SyntaxError(EOFWhileParsingString, 1, 5)));
2760
2761         assert_eq!(from_str("\"\""), Ok(String("".to_string())));
2762         assert_eq!(from_str("\"foo\""), Ok(String("foo".to_string())));
2763         assert_eq!(from_str("\"\\\"\""), Ok(String("\"".to_string())));
2764         assert_eq!(from_str("\"\\b\""), Ok(String("\x08".to_string())));
2765         assert_eq!(from_str("\"\\n\""), Ok(String("\n".to_string())));
2766         assert_eq!(from_str("\"\\r\""), Ok(String("\r".to_string())));
2767         assert_eq!(from_str("\"\\t\""), Ok(String("\t".to_string())));
2768         assert_eq!(from_str(" \"foo\" "), Ok(String("foo".to_string())));
2769         assert_eq!(from_str("\"\\u12ab\""), Ok(String("\u12ab".to_string())));
2770         assert_eq!(from_str("\"\\uAB12\""), Ok(String("\uAB12".to_string())));
2771     }
2772
2773     #[test]
2774     fn test_decode_str() {
2775         let s = [("\"\"", ""),
2776                  ("\"foo\"", "foo"),
2777                  ("\"\\\"\"", "\""),
2778                  ("\"\\b\"", "\x08"),
2779                  ("\"\\n\"", "\n"),
2780                  ("\"\\r\"", "\r"),
2781                  ("\"\\t\"", "\t"),
2782                  ("\"\\u12ab\"", "\u12ab"),
2783                  ("\"\\uAB12\"", "\uAB12")];
2784
2785         for &(i, o) in s.iter() {
2786             let v: String = super::decode(i).unwrap();
2787             assert_eq!(v.as_slice(), o);
2788         }
2789     }
2790
2791     #[test]
2792     fn test_read_list() {
2793         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
2794         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingList,  1, 3)));
2795         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
2796         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
2797         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
2798
2799         assert_eq!(from_str("[]"), Ok(List(vec![])));
2800         assert_eq!(from_str("[ ]"), Ok(List(vec![])));
2801         assert_eq!(from_str("[true]"), Ok(List(vec![Boolean(true)])));
2802         assert_eq!(from_str("[ false ]"), Ok(List(vec![Boolean(false)])));
2803         assert_eq!(from_str("[null]"), Ok(List(vec![Null])));
2804         assert_eq!(from_str("[3, 1]"),
2805                      Ok(List(vec![U64(3), U64(1)])));
2806         assert_eq!(from_str("\n[3, 2]\n"),
2807                      Ok(List(vec![U64(3), U64(2)])));
2808         assert_eq!(from_str("[2, [4, 1]]"),
2809                Ok(List(vec![U64(2), List(vec![U64(4), U64(1)])])));
2810     }
2811
2812     #[test]
2813     fn test_decode_list() {
2814         let v: Vec<()> = super::decode("[]").unwrap();
2815         assert_eq!(v, vec![]);
2816
2817         let v: Vec<()> = super::decode("[null]").unwrap();
2818         assert_eq!(v, vec![()]);
2819
2820         let v: Vec<bool> = super::decode("[true]").unwrap();
2821         assert_eq!(v, vec![true]);
2822
2823         let v: Vec<int> = super::decode("[3, 1]").unwrap();
2824         assert_eq!(v, vec![3, 1]);
2825
2826         let v: Vec<Vec<uint>> = super::decode("[[3], [1, 2]]").unwrap();
2827         assert_eq!(v, vec![vec![3], vec![1, 2]]);
2828     }
2829
2830     #[test]
2831     fn test_read_object() {
2832         assert_eq!(from_str("{"),       Err(SyntaxError(EOFWhileParsingObject, 1, 2)));
2833         assert_eq!(from_str("{ "),      Err(SyntaxError(EOFWhileParsingObject, 1, 3)));
2834         assert_eq!(from_str("{1"),      Err(SyntaxError(KeyMustBeAString,      1, 2)));
2835         assert_eq!(from_str("{ \"a\""), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
2836         assert_eq!(from_str("{\"a\""),  Err(SyntaxError(EOFWhileParsingObject, 1, 5)));
2837         assert_eq!(from_str("{\"a\" "), Err(SyntaxError(EOFWhileParsingObject, 1, 6)));
2838
2839         assert_eq!(from_str("{\"a\" 1"),   Err(SyntaxError(ExpectedColon,         1, 6)));
2840         assert_eq!(from_str("{\"a\":"),    Err(SyntaxError(EOFWhileParsingValue,  1, 6)));
2841         assert_eq!(from_str("{\"a\":1"),   Err(SyntaxError(EOFWhileParsingObject, 1, 7)));
2842         assert_eq!(from_str("{\"a\":1 1"), Err(SyntaxError(InvalidSyntax,         1, 8)));
2843         assert_eq!(from_str("{\"a\":1,"),  Err(SyntaxError(EOFWhileParsingObject, 1, 8)));
2844
2845         assert_eq!(from_str("{}").unwrap(), mk_object([]));
2846         assert_eq!(from_str("{\"a\": 3}").unwrap(),
2847                   mk_object([("a".to_string(), U64(3))]));
2848
2849         assert_eq!(from_str(
2850                       "{ \"a\": null, \"b\" : true }").unwrap(),
2851                   mk_object([
2852                       ("a".to_string(), Null),
2853                       ("b".to_string(), Boolean(true))]));
2854         assert_eq!(from_str("\n{ \"a\": null, \"b\" : true }\n").unwrap(),
2855                   mk_object([
2856                       ("a".to_string(), Null),
2857                       ("b".to_string(), Boolean(true))]));
2858         assert_eq!(from_str(
2859                       "{\"a\" : 1.0 ,\"b\": [ true ]}").unwrap(),
2860                   mk_object([
2861                       ("a".to_string(), F64(1.0)),
2862                       ("b".to_string(), List(vec![Boolean(true)]))
2863                   ]));
2864         assert_eq!(from_str(
2865                       "{\
2866                           \"a\": 1.0, \
2867                           \"b\": [\
2868                               true,\
2869                               \"foo\\nbar\", \
2870                               { \"c\": {\"d\": null} } \
2871                           ]\
2872                       }").unwrap(),
2873                   mk_object([
2874                       ("a".to_string(), F64(1.0)),
2875                       ("b".to_string(), List(vec![
2876                           Boolean(true),
2877                           String("foo\nbar".to_string()),
2878                           mk_object([
2879                               ("c".to_string(), mk_object([("d".to_string(), Null)]))
2880                           ])
2881                       ]))
2882                   ]));
2883     }
2884
2885     #[test]
2886     fn test_decode_struct() {
2887         let s = "{
2888             \"inner\": [
2889                 { \"a\": null, \"b\": 2, \"c\": [\"abc\", \"xyz\"] }
2890             ]
2891         }";
2892
2893         let v: Outer = super::decode(s).unwrap();
2894         assert_eq!(
2895             v,
2896             Outer {
2897                 inner: vec![
2898                     Inner { a: (), b: 2, c: vec!["abc".to_string(), "xyz".to_string()] }
2899                 ]
2900             }
2901         );
2902     }
2903
2904     #[deriving(Decodable)]
2905     struct FloatStruct {
2906         f: f64,
2907         a: Vec<f64>
2908     }
2909     #[test]
2910     fn test_decode_struct_with_nan() {
2911         let s = "{\"f\":null,\"a\":[null,123]}";
2912         let obj: FloatStruct = super::decode(s).unwrap();
2913         assert!(obj.f.is_nan());
2914         assert!(obj.a.get(0).is_nan());
2915         assert_eq!(obj.a.get(1), &123f64);
2916     }
2917
2918     #[test]
2919     fn test_decode_option() {
2920         let value: Option<String> = super::decode("null").unwrap();
2921         assert_eq!(value, None);
2922
2923         let value: Option<String> = super::decode("\"jodhpurs\"").unwrap();
2924         assert_eq!(value, Some("jodhpurs".to_string()));
2925     }
2926
2927     #[test]
2928     fn test_decode_enum() {
2929         let value: Animal = super::decode("\"Dog\"").unwrap();
2930         assert_eq!(value, Dog);
2931
2932         let s = "{\"variant\":\"Frog\",\"fields\":[\"Henry\",349]}";
2933         let value: Animal = super::decode(s).unwrap();
2934         assert_eq!(value, Frog("Henry".to_string(), 349));
2935     }
2936
2937     #[test]
2938     fn test_decode_map() {
2939         let s = "{\"a\": \"Dog\", \"b\": {\"variant\":\"Frog\",\
2940                   \"fields\":[\"Henry\", 349]}}";
2941         let mut map: TreeMap<String, Animal> = super::decode(s).unwrap();
2942
2943         assert_eq!(map.pop(&"a".to_string()), Some(Dog));
2944         assert_eq!(map.pop(&"b".to_string()), Some(Frog("Henry".to_string(), 349)));
2945     }
2946
2947     #[test]
2948     fn test_multiline_errors() {
2949         assert_eq!(from_str("{\n  \"foo\":\n \"bar\""),
2950             Err(SyntaxError(EOFWhileParsingObject, 3u, 8u)));
2951     }
2952
2953     #[deriving(Decodable)]
2954     #[allow(dead_code)]
2955     struct DecodeStruct {
2956         x: f64,
2957         y: bool,
2958         z: String,
2959         w: Vec<DecodeStruct>
2960     }
2961     #[deriving(Decodable)]
2962     enum DecodeEnum {
2963         A(f64),
2964         B(String)
2965     }
2966     fn check_err<T: Decodable<Decoder, DecoderError>>(to_parse: &'static str,
2967                                                       expected: DecoderError) {
2968         let res: DecodeResult<T> = match from_str(to_parse) {
2969             Err(e) => Err(ParseError(e)),
2970             Ok(json) => Decodable::decode(&mut Decoder::new(json))
2971         };
2972         match res {
2973             Ok(_) => fail!("`{}` parsed & decoded ok, expecting error `{}`",
2974                               to_parse, expected),
2975             Err(ParseError(e)) => fail!("`{}` is not valid json: {}",
2976                                            to_parse, e),
2977             Err(e) => {
2978                 assert_eq!(e, expected);
2979             }
2980         }
2981     }
2982     #[test]
2983     fn test_decode_errors_struct() {
2984         check_err::<DecodeStruct>("[]", ExpectedError("Object".to_string(), "[]".to_string()));
2985         check_err::<DecodeStruct>("{\"x\": true, \"y\": true, \"z\": \"\", \"w\": []}",
2986                                   ExpectedError("Number".to_string(), "true".to_string()));
2987         check_err::<DecodeStruct>("{\"x\": 1, \"y\": [], \"z\": \"\", \"w\": []}",
2988                                   ExpectedError("Boolean".to_string(), "[]".to_string()));
2989         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": {}, \"w\": []}",
2990                                   ExpectedError("String".to_string(), "{}".to_string()));
2991         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\", \"w\": null}",
2992                                   ExpectedError("List".to_string(), "null".to_string()));
2993         check_err::<DecodeStruct>("{\"x\": 1, \"y\": true, \"z\": \"\"}",
2994                                   MissingFieldError("w".to_string()));
2995     }
2996     #[test]
2997     fn test_decode_errors_enum() {
2998         check_err::<DecodeEnum>("{}",
2999                                 MissingFieldError("variant".to_string()));
3000         check_err::<DecodeEnum>("{\"variant\": 1}",
3001                                 ExpectedError("String".to_string(), "1".to_string()));
3002         check_err::<DecodeEnum>("{\"variant\": \"A\"}",
3003                                 MissingFieldError("fields".to_string()));
3004         check_err::<DecodeEnum>("{\"variant\": \"A\", \"fields\": null}",
3005                                 ExpectedError("List".to_string(), "null".to_string()));
3006         check_err::<DecodeEnum>("{\"variant\": \"C\", \"fields\": []}",
3007                                 UnknownVariantError("C".to_string()));
3008     }
3009
3010     #[test]
3011     fn test_find(){
3012         let json_value = from_str("{\"dog\" : \"cat\"}").unwrap();
3013         let found_str = json_value.find(&"dog".to_string());
3014         assert!(found_str.is_some() && found_str.unwrap().as_string().unwrap() == "cat");
3015     }
3016
3017     #[test]
3018     fn test_find_path(){
3019         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
3020         let found_str = json_value.find_path(&[&"dog".to_string(),
3021                                              &"cat".to_string(), &"mouse".to_string()]);
3022         assert!(found_str.is_some() && found_str.unwrap().as_string().unwrap() == "cheese");
3023     }
3024
3025     #[test]
3026     fn test_search(){
3027         let json_value = from_str("{\"dog\":{\"cat\": {\"mouse\" : \"cheese\"}}}").unwrap();
3028         let found_str = json_value.search(&"mouse".to_string()).and_then(|j| j.as_string());
3029         assert!(found_str.is_some());
3030         assert!(found_str.unwrap() == "cheese");
3031     }
3032
3033     #[test]
3034     fn test_is_object(){
3035         let json_value = from_str("{}").unwrap();
3036         assert!(json_value.is_object());
3037     }
3038
3039     #[test]
3040     fn test_as_object(){
3041         let json_value = from_str("{}").unwrap();
3042         let json_object = json_value.as_object();
3043         assert!(json_object.is_some());
3044     }
3045
3046     #[test]
3047     fn test_is_list(){
3048         let json_value = from_str("[1, 2, 3]").unwrap();
3049         assert!(json_value.is_list());
3050     }
3051
3052     #[test]
3053     fn test_as_list(){
3054         let json_value = from_str("[1, 2, 3]").unwrap();
3055         let json_list = json_value.as_list();
3056         let expected_length = 3;
3057         assert!(json_list.is_some() && json_list.unwrap().len() == expected_length);
3058     }
3059
3060     #[test]
3061     fn test_is_string(){
3062         let json_value = from_str("\"dog\"").unwrap();
3063         assert!(json_value.is_string());
3064     }
3065
3066     #[test]
3067     fn test_as_string(){
3068         let json_value = from_str("\"dog\"").unwrap();
3069         let json_str = json_value.as_string();
3070         let expected_str = "dog";
3071         assert_eq!(json_str, Some(expected_str));
3072     }
3073
3074     #[test]
3075     fn test_is_number(){
3076         let json_value = from_str("12").unwrap();
3077         assert!(json_value.is_number());
3078     }
3079
3080     #[test]
3081     fn test_is_i64(){
3082         let json_value = from_str("-12").unwrap();
3083         assert!(json_value.is_i64());
3084
3085         let json_value = from_str("12").unwrap();
3086         assert!(!json_value.is_i64());
3087
3088         let json_value = from_str("12.0").unwrap();
3089         assert!(!json_value.is_i64());
3090     }
3091
3092     #[test]
3093     fn test_is_u64(){
3094         let json_value = from_str("12").unwrap();
3095         assert!(json_value.is_u64());
3096
3097         let json_value = from_str("-12").unwrap();
3098         assert!(!json_value.is_u64());
3099
3100         let json_value = from_str("12.0").unwrap();
3101         assert!(!json_value.is_u64());
3102     }
3103
3104     #[test]
3105     fn test_is_f64(){
3106         let json_value = from_str("12").unwrap();
3107         assert!(!json_value.is_f64());
3108
3109         let json_value = from_str("-12").unwrap();
3110         assert!(!json_value.is_f64());
3111
3112         let json_value = from_str("12.0").unwrap();
3113         assert!(json_value.is_f64());
3114
3115         let json_value = from_str("-12.0").unwrap();
3116         assert!(json_value.is_f64());
3117     }
3118
3119     #[test]
3120     fn test_as_i64(){
3121         let json_value = from_str("-12").unwrap();
3122         let json_num = json_value.as_i64();
3123         assert_eq!(json_num, Some(-12));
3124     }
3125
3126     #[test]
3127     fn test_as_u64(){
3128         let json_value = from_str("12").unwrap();
3129         let json_num = json_value.as_u64();
3130         assert_eq!(json_num, Some(12));
3131     }
3132
3133     #[test]
3134     fn test_as_f64(){
3135         let json_value = from_str("12.0").unwrap();
3136         let json_num = json_value.as_f64();
3137         assert_eq!(json_num, Some(12f64));
3138     }
3139
3140     #[test]
3141     fn test_is_boolean(){
3142         let json_value = from_str("false").unwrap();
3143         assert!(json_value.is_boolean());
3144     }
3145
3146     #[test]
3147     fn test_as_boolean(){
3148         let json_value = from_str("false").unwrap();
3149         let json_bool = json_value.as_boolean();
3150         let expected_bool = false;
3151         assert!(json_bool.is_some() && json_bool.unwrap() == expected_bool);
3152     }
3153
3154     #[test]
3155     fn test_is_null(){
3156         let json_value = from_str("null").unwrap();
3157         assert!(json_value.is_null());
3158     }
3159
3160     #[test]
3161     fn test_as_null(){
3162         let json_value = from_str("null").unwrap();
3163         let json_null = json_value.as_null();
3164         let expected_null = ();
3165         assert!(json_null.is_some() && json_null.unwrap() == expected_null);
3166     }
3167
3168     #[test]
3169     fn test_encode_hashmap_with_numeric_key() {
3170         use std::str::from_utf8;
3171         use std::io::Writer;
3172         use std::io::MemWriter;
3173         use std::collections::HashMap;
3174         let mut hm: HashMap<uint, bool> = HashMap::new();
3175         hm.insert(1, true);
3176         let mut mem_buf = MemWriter::new();
3177         {
3178             let mut encoder = Encoder::new(&mut mem_buf as &mut io::Writer);
3179             hm.encode(&mut encoder).unwrap();
3180         }
3181         let bytes = mem_buf.unwrap();
3182         let json_str = from_utf8(bytes.as_slice()).unwrap();
3183         match from_str(json_str) {
3184             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3185             _ => {} // it parsed and we are good to go
3186         }
3187     }
3188
3189     #[test]
3190     fn test_prettyencode_hashmap_with_numeric_key() {
3191         use std::str::from_utf8;
3192         use std::io::Writer;
3193         use std::io::MemWriter;
3194         use std::collections::HashMap;
3195         let mut hm: HashMap<uint, bool> = HashMap::new();
3196         hm.insert(1, true);
3197         let mut mem_buf = MemWriter::new();
3198         {
3199             let mut encoder = PrettyEncoder::new(&mut mem_buf as &mut io::Writer);
3200             hm.encode(&mut encoder).unwrap()
3201         }
3202         let bytes = mem_buf.unwrap();
3203         let json_str = from_utf8(bytes.as_slice()).unwrap();
3204         match from_str(json_str) {
3205             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3206             _ => {} // it parsed and we are good to go
3207         }
3208     }
3209
3210     #[test]
3211     fn test_prettyencoder_indent_level_param() {
3212         use std::str::from_utf8;
3213         use std::io::MemWriter;
3214         use std::collections::TreeMap;
3215
3216         let mut tree = TreeMap::new();
3217
3218         tree.insert("hello".into_string(), String("guten tag".into_string()));
3219         tree.insert("goodbye".into_string(), String("sayonara".into_string()));
3220
3221         let json = List(
3222             // The following layout below should look a lot like
3223             // the pretty-printed JSON (indent * x)
3224             vec!
3225             ( // 0x
3226                 String("greetings".into_string()), // 1x
3227                 Object(tree), // 1x + 2x + 2x + 1x
3228             ) // 0x
3229             // End JSON list (7 lines)
3230         );
3231
3232         // Helper function for counting indents
3233         fn indents(source: &str) -> uint {
3234             let trimmed = source.trim_left_chars(' ');
3235             source.len() - trimmed.len()
3236         }
3237
3238         // Test up to 4 spaces of indents (more?)
3239         for i in range(0, 4u) {
3240             let mut writer = MemWriter::new();
3241             {
3242                 let ref mut encoder = PrettyEncoder::new(&mut writer);
3243                 encoder.set_indent(i);
3244                 json.encode(encoder).unwrap();
3245             }
3246
3247             let bytes = writer.unwrap();
3248             let printed = from_utf8(bytes.as_slice()).unwrap();
3249
3250             // Check for indents at each line
3251             let lines: Vec<&str> = printed.lines().collect();
3252             assert_eq!(lines.len(), 7); // JSON should be 7 lines
3253
3254             assert_eq!(indents(lines[0]), 0 * i); // [
3255             assert_eq!(indents(lines[1]), 1 * i); //   "greetings",
3256             assert_eq!(indents(lines[2]), 1 * i); //   {
3257             assert_eq!(indents(lines[3]), 2 * i); //     "hello": "guten tag",
3258             assert_eq!(indents(lines[4]), 2 * i); //     "goodbye": "sayonara"
3259             assert_eq!(indents(lines[5]), 1 * i); //   },
3260             assert_eq!(indents(lines[6]), 0 * i); // ]
3261
3262             // Finally, test that the pretty-printed JSON is valid
3263             from_str(printed).ok().expect("Pretty-printed JSON is invalid!");
3264         }
3265     }
3266
3267     #[test]
3268     fn test_hashmap_with_numeric_key_can_handle_double_quote_delimited_key() {
3269         use std::collections::HashMap;
3270         use Decodable;
3271         let json_str = "{\"1\":true}";
3272         let json_obj = match from_str(json_str) {
3273             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3274             Ok(o) => o
3275         };
3276         let mut decoder = Decoder::new(json_obj);
3277         let _hm: HashMap<uint, bool> = Decodable::decode(&mut decoder).unwrap();
3278     }
3279
3280     #[test]
3281     fn test_hashmap_with_numeric_key_will_error_with_string_keys() {
3282         use std::collections::HashMap;
3283         use Decodable;
3284         let json_str = "{\"a\":true}";
3285         let json_obj = match from_str(json_str) {
3286             Err(_) => fail!("Unable to parse json_str: {}", json_str),
3287             Ok(o) => o
3288         };
3289         let mut decoder = Decoder::new(json_obj);
3290         let result: Result<HashMap<uint, bool>, DecoderError> = Decodable::decode(&mut decoder);
3291         assert_eq!(result, Err(ExpectedError("Number".to_string(), "a".to_string())));
3292     }
3293
3294     fn assert_stream_equal(src: &str,
3295                            expected: Vec<(JsonEvent, Vec<StackElement>)>) {
3296         let mut parser = Parser::new(src.chars());
3297         let mut i = 0;
3298         loop {
3299             let evt = match parser.next() {
3300                 Some(e) => e,
3301                 None => { break; }
3302             };
3303             let (ref expected_evt, ref expected_stack) = expected[i];
3304             if !parser.stack().is_equal_to(expected_stack.as_slice()) {
3305                 fail!("Parser stack is not equal to {}", expected_stack);
3306             }
3307             assert_eq!(&evt, expected_evt);
3308             i+=1;
3309         }
3310     }
3311     #[test]
3312     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
3313     fn test_streaming_parser() {
3314         assert_stream_equal(
3315             r#"{ "foo":"bar", "array" : [0, 1, 2, 3, 4, 5], "idents":[null,true,false]}"#,
3316             vec![
3317                 (ObjectStart,             vec![]),
3318                   (StringValue("bar".to_string()),   vec![Key("foo")]),
3319                   (ListStart,             vec![Key("array")]),
3320                     (U64Value(0),         vec![Key("array"), Index(0)]),
3321                     (U64Value(1),         vec![Key("array"), Index(1)]),
3322                     (U64Value(2),         vec![Key("array"), Index(2)]),
3323                     (U64Value(3),         vec![Key("array"), Index(3)]),
3324                     (U64Value(4),         vec![Key("array"), Index(4)]),
3325                     (U64Value(5),         vec![Key("array"), Index(5)]),
3326                   (ListEnd,               vec![Key("array")]),
3327                   (ListStart,             vec![Key("idents")]),
3328                     (NullValue,           vec![Key("idents"), Index(0)]),
3329                     (BooleanValue(true),  vec![Key("idents"), Index(1)]),
3330                     (BooleanValue(false), vec![Key("idents"), Index(2)]),
3331                   (ListEnd,               vec![Key("idents")]),
3332                 (ObjectEnd,               vec![]),
3333             ]
3334         );
3335     }
3336     fn last_event(src: &str) -> JsonEvent {
3337         let mut parser = Parser::new(src.chars());
3338         let mut evt = NullValue;
3339         loop {
3340             evt = match parser.next() {
3341                 Some(e) => e,
3342                 None => return evt,
3343             }
3344         }
3345     }
3346     #[test]
3347     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
3348     fn test_read_object_streaming() {
3349         assert_eq!(last_event("{ "),      Error(SyntaxError(EOFWhileParsingObject, 1, 3)));
3350         assert_eq!(last_event("{1"),      Error(SyntaxError(KeyMustBeAString,      1, 2)));
3351         assert_eq!(last_event("{ \"a\""), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
3352         assert_eq!(last_event("{\"a\""),  Error(SyntaxError(EOFWhileParsingObject, 1, 5)));
3353         assert_eq!(last_event("{\"a\" "), Error(SyntaxError(EOFWhileParsingObject, 1, 6)));
3354
3355         assert_eq!(last_event("{\"a\" 1"),   Error(SyntaxError(ExpectedColon,         1, 6)));
3356         assert_eq!(last_event("{\"a\":"),    Error(SyntaxError(EOFWhileParsingValue,  1, 6)));
3357         assert_eq!(last_event("{\"a\":1"),   Error(SyntaxError(EOFWhileParsingObject, 1, 7)));
3358         assert_eq!(last_event("{\"a\":1 1"), Error(SyntaxError(InvalidSyntax,         1, 8)));
3359         assert_eq!(last_event("{\"a\":1,"),  Error(SyntaxError(EOFWhileParsingObject, 1, 8)));
3360
3361         assert_stream_equal(
3362             "{}",
3363             vec![(ObjectStart, vec![]), (ObjectEnd, vec![])]
3364         );
3365         assert_stream_equal(
3366             "{\"a\": 3}",
3367             vec![
3368                 (ObjectStart,        vec![]),
3369                   (U64Value(3),      vec![Key("a")]),
3370                 (ObjectEnd,          vec![]),
3371             ]
3372         );
3373         assert_stream_equal(
3374             "{ \"a\": null, \"b\" : true }",
3375             vec![
3376                 (ObjectStart,           vec![]),
3377                   (NullValue,           vec![Key("a")]),
3378                   (BooleanValue(true),  vec![Key("b")]),
3379                 (ObjectEnd,             vec![]),
3380             ]
3381         );
3382         assert_stream_equal(
3383             "{\"a\" : 1.0 ,\"b\": [ true ]}",
3384             vec![
3385                 (ObjectStart,           vec![]),
3386                   (F64Value(1.0),       vec![Key("a")]),
3387                   (ListStart,           vec![Key("b")]),
3388                     (BooleanValue(true),vec![Key("b"), Index(0)]),
3389                   (ListEnd,             vec![Key("b")]),
3390                 (ObjectEnd,             vec![]),
3391             ]
3392         );
3393         assert_stream_equal(
3394             r#"{
3395                 "a": 1.0,
3396                 "b": [
3397                     true,
3398                     "foo\nbar",
3399                     { "c": {"d": null} }
3400                 ]
3401             }"#,
3402             vec![
3403                 (ObjectStart,                   vec![]),
3404                   (F64Value(1.0),               vec![Key("a")]),
3405                   (ListStart,                   vec![Key("b")]),
3406                     (BooleanValue(true),        vec![Key("b"), Index(0)]),
3407                     (StringValue("foo\nbar".to_string()),  vec![Key("b"), Index(1)]),
3408                     (ObjectStart,               vec![Key("b"), Index(2)]),
3409                       (ObjectStart,             vec![Key("b"), Index(2), Key("c")]),
3410                         (NullValue,             vec![Key("b"), Index(2), Key("c"), Key("d")]),
3411                       (ObjectEnd,               vec![Key("b"), Index(2), Key("c")]),
3412                     (ObjectEnd,                 vec![Key("b"), Index(2)]),
3413                   (ListEnd,                     vec![Key("b")]),
3414                 (ObjectEnd,                     vec![]),
3415             ]
3416         );
3417     }
3418     #[test]
3419     #[ignore(cfg(target_word_size = "32"))] // FIXME(#14064)
3420     fn test_read_list_streaming() {
3421         assert_stream_equal(
3422             "[]",
3423             vec![
3424                 (ListStart, vec![]),
3425                 (ListEnd,   vec![]),
3426             ]
3427         );
3428         assert_stream_equal(
3429             "[ ]",
3430             vec![
3431                 (ListStart, vec![]),
3432                 (ListEnd,   vec![]),
3433             ]
3434         );
3435         assert_stream_equal(
3436             "[true]",
3437             vec![
3438                 (ListStart,              vec![]),
3439                     (BooleanValue(true), vec![Index(0)]),
3440                 (ListEnd,                vec![]),
3441             ]
3442         );
3443         assert_stream_equal(
3444             "[ false ]",
3445             vec![
3446                 (ListStart,               vec![]),
3447                     (BooleanValue(false), vec![Index(0)]),
3448                 (ListEnd,                 vec![]),
3449             ]
3450         );
3451         assert_stream_equal(
3452             "[null]",
3453             vec![
3454                 (ListStart,     vec![]),
3455                     (NullValue, vec![Index(0)]),
3456                 (ListEnd,       vec![]),
3457             ]
3458         );
3459         assert_stream_equal(
3460             "[3, 1]",
3461             vec![
3462                 (ListStart,     vec![]),
3463                     (U64Value(3), vec![Index(0)]),
3464                     (U64Value(1), vec![Index(1)]),
3465                 (ListEnd,       vec![]),
3466             ]
3467         );
3468         assert_stream_equal(
3469             "\n[3, 2]\n",
3470             vec![
3471                 (ListStart,     vec![]),
3472                     (U64Value(3), vec![Index(0)]),
3473                     (U64Value(2), vec![Index(1)]),
3474                 (ListEnd,       vec![]),
3475             ]
3476         );
3477         assert_stream_equal(
3478             "[2, [4, 1]]",
3479             vec![
3480                 (ListStart,            vec![]),
3481                     (U64Value(2),      vec![Index(0)]),
3482                     (ListStart,        vec![Index(1)]),
3483                         (U64Value(4),  vec![Index(1), Index(0)]),
3484                         (U64Value(1),  vec![Index(1), Index(1)]),
3485                     (ListEnd,          vec![Index(1)]),
3486                 (ListEnd,              vec![]),
3487             ]
3488         );
3489
3490         assert_eq!(last_event("["), Error(SyntaxError(EOFWhileParsingValue, 1,  2)));
3491
3492         assert_eq!(from_str("["),     Err(SyntaxError(EOFWhileParsingValue, 1, 2)));
3493         assert_eq!(from_str("[1"),    Err(SyntaxError(EOFWhileParsingList,  1, 3)));
3494         assert_eq!(from_str("[1,"),   Err(SyntaxError(EOFWhileParsingValue, 1, 4)));
3495         assert_eq!(from_str("[1,]"),  Err(SyntaxError(InvalidSyntax,        1, 4)));
3496         assert_eq!(from_str("[6 7]"), Err(SyntaxError(InvalidSyntax,        1, 4)));
3497
3498     }
3499     #[test]
3500     fn test_trailing_characters_streaming() {
3501         assert_eq!(last_event("nulla"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3502         assert_eq!(last_event("truea"),  Error(SyntaxError(TrailingCharacters, 1, 5)));
3503         assert_eq!(last_event("falsea"), Error(SyntaxError(TrailingCharacters, 1, 6)));
3504         assert_eq!(last_event("1a"),     Error(SyntaxError(TrailingCharacters, 1, 2)));
3505         assert_eq!(last_event("[]a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3506         assert_eq!(last_event("{}a"),    Error(SyntaxError(TrailingCharacters, 1, 3)));
3507     }
3508     #[test]
3509     fn test_read_identifiers_streaming() {
3510         assert_eq!(Parser::new("null".chars()).next(), Some(NullValue));
3511         assert_eq!(Parser::new("true".chars()).next(), Some(BooleanValue(true)));
3512         assert_eq!(Parser::new("false".chars()).next(), Some(BooleanValue(false)));
3513
3514         assert_eq!(last_event("n"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3515         assert_eq!(last_event("nul"),  Error(SyntaxError(InvalidSyntax, 1, 4)));
3516         assert_eq!(last_event("t"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3517         assert_eq!(last_event("truz"), Error(SyntaxError(InvalidSyntax, 1, 4)));
3518         assert_eq!(last_event("f"),    Error(SyntaxError(InvalidSyntax, 1, 2)));
3519         assert_eq!(last_event("faz"),  Error(SyntaxError(InvalidSyntax, 1, 3)));
3520     }
3521
3522     #[test]
3523     fn test_stack() {
3524         let mut stack = Stack::new();
3525
3526         assert!(stack.is_empty());
3527         assert!(stack.len() == 0);
3528         assert!(!stack.last_is_index());
3529
3530         stack.push_index(0);
3531         stack.bump_index();
3532
3533         assert!(stack.len() == 1);
3534         assert!(stack.is_equal_to([Index(1)]));
3535         assert!(stack.starts_with([Index(1)]));
3536         assert!(stack.ends_with([Index(1)]));
3537         assert!(stack.last_is_index());
3538         assert!(stack.get(0) == Index(1));
3539
3540         stack.push_key("foo".to_string());
3541
3542         assert!(stack.len() == 2);
3543         assert!(stack.is_equal_to([Index(1), Key("foo")]));
3544         assert!(stack.starts_with([Index(1), Key("foo")]));
3545         assert!(stack.starts_with([Index(1)]));
3546         assert!(stack.ends_with([Index(1), Key("foo")]));
3547         assert!(stack.ends_with([Key("foo")]));
3548         assert!(!stack.last_is_index());
3549         assert!(stack.get(0) == Index(1));
3550         assert!(stack.get(1) == Key("foo"));
3551
3552         stack.push_key("bar".to_string());
3553
3554         assert!(stack.len() == 3);
3555         assert!(stack.is_equal_to([Index(1), Key("foo"), Key("bar")]));
3556         assert!(stack.starts_with([Index(1)]));
3557         assert!(stack.starts_with([Index(1), Key("foo")]));
3558         assert!(stack.starts_with([Index(1), Key("foo"), Key("bar")]));
3559         assert!(stack.ends_with([Key("bar")]));
3560         assert!(stack.ends_with([Key("foo"), Key("bar")]));
3561         assert!(stack.ends_with([Index(1), Key("foo"), Key("bar")]));
3562         assert!(!stack.last_is_index());
3563         assert!(stack.get(0) == Index(1));
3564         assert!(stack.get(1) == Key("foo"));
3565         assert!(stack.get(2) == Key("bar"));
3566
3567         stack.pop();
3568
3569         assert!(stack.len() == 2);
3570         assert!(stack.is_equal_to([Index(1), Key("foo")]));
3571         assert!(stack.starts_with([Index(1), Key("foo")]));
3572         assert!(stack.starts_with([Index(1)]));
3573         assert!(stack.ends_with([Index(1), Key("foo")]));
3574         assert!(stack.ends_with([Key("foo")]));
3575         assert!(!stack.last_is_index());
3576         assert!(stack.get(0) == Index(1));
3577         assert!(stack.get(1) == Key("foo"));
3578     }
3579
3580     #[test]
3581     fn test_to_json() {
3582         use std::collections::{HashMap,TreeMap};
3583         use super::ToJson;
3584
3585         let list2 = List(vec!(U64(1), U64(2)));
3586         let list3 = List(vec!(U64(1), U64(2), U64(3)));
3587         let object = {
3588             let mut tree_map = TreeMap::new();
3589             tree_map.insert("a".to_string(), U64(1));
3590             tree_map.insert("b".to_string(), U64(2));
3591             Object(tree_map)
3592         };
3593
3594         assert_eq!(list2.to_json(), list2);
3595         assert_eq!(object.to_json(), object);
3596         assert_eq!(3_i.to_json(), I64(3));
3597         assert_eq!(4_i8.to_json(), I64(4));
3598         assert_eq!(5_i16.to_json(), I64(5));
3599         assert_eq!(6_i32.to_json(), I64(6));
3600         assert_eq!(7_i64.to_json(), I64(7));
3601         assert_eq!(8_u.to_json(), U64(8));
3602         assert_eq!(9_u8.to_json(), U64(9));
3603         assert_eq!(10_u16.to_json(), U64(10));
3604         assert_eq!(11_u32.to_json(), U64(11));
3605         assert_eq!(12_u64.to_json(), U64(12));
3606         assert_eq!(13.0_f32.to_json(), F64(13.0_f64));
3607         assert_eq!(14.0_f64.to_json(), F64(14.0_f64));
3608         assert_eq!(().to_json(), Null);
3609         assert_eq!(f32::INFINITY.to_json(), Null);
3610         assert_eq!(f64::NAN.to_json(), Null);
3611         assert_eq!(true.to_json(), Boolean(true));
3612         assert_eq!(false.to_json(), Boolean(false));
3613         assert_eq!("abc".to_string().to_json(), String("abc".to_string()));
3614         assert_eq!((1u, 2u).to_json(), list2);
3615         assert_eq!((1u, 2u, 3u).to_json(), list3);
3616         assert_eq!([1u, 2].to_json(), list2);
3617         assert_eq!((&[1u, 2, 3]).to_json(), list3);
3618         assert_eq!((vec![1u, 2]).to_json(), list2);
3619         assert_eq!(vec!(1u, 2, 3).to_json(), list3);
3620         let mut tree_map = TreeMap::new();
3621         tree_map.insert("a".to_string(), 1u);
3622         tree_map.insert("b".to_string(), 2);
3623         assert_eq!(tree_map.to_json(), object);
3624         let mut hash_map = HashMap::new();
3625         hash_map.insert("a".to_string(), 1u);
3626         hash_map.insert("b".to_string(), 2);
3627         assert_eq!(hash_map.to_json(), object);
3628         assert_eq!(Some(15i).to_json(), I64(15));
3629         assert_eq!(Some(15u).to_json(), U64(15));
3630         assert_eq!(None::<int>.to_json(), Null);
3631     }
3632
3633     #[bench]
3634     fn bench_streaming_small(b: &mut Bencher) {
3635         b.iter( || {
3636             let mut parser = Parser::new(
3637                 r#"{
3638                     "a": 1.0,
3639                     "b": [
3640                         true,
3641                         "foo\nbar",
3642                         { "c": {"d": null} }
3643                     ]
3644                 }"#.chars()
3645             );
3646             loop {
3647                 match parser.next() {
3648                     None => return,
3649                     _ => {}
3650                 }
3651             }
3652         });
3653     }
3654     #[bench]
3655     fn bench_small(b: &mut Bencher) {
3656         b.iter( || {
3657             let _ = from_str(r#"{
3658                 "a": 1.0,
3659                 "b": [
3660                     true,
3661                     "foo\nbar",
3662                     { "c": {"d": null} }
3663                 ]
3664             }"#);
3665         });
3666     }
3667
3668     fn big_json() -> String {
3669         let mut src = "[\n".to_string();
3670         for _ in range(0i, 500) {
3671             src.push_str(r#"{ "a": true, "b": null, "c":3.1415, "d": "Hello world", "e": \
3672                             [1,2,3]},"#);
3673         }
3674         src.push_str("{}]");
3675         return src;
3676     }
3677
3678     #[bench]
3679     fn bench_streaming_large(b: &mut Bencher) {
3680         let src = big_json();
3681         b.iter( || {
3682             let mut parser = Parser::new(src.as_slice().chars());
3683             loop {
3684                 match parser.next() {
3685                     None => return,
3686                     _ => {}
3687                 }
3688             }
3689         });
3690     }
3691     #[bench]
3692     fn bench_large(b: &mut Bencher) {
3693         let src = big_json();
3694         b.iter( || { let _ = from_str(src.as_slice()); });
3695     }
3696 }