src/libserialize/json.rs

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