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