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