json.rs

// Rust JSON serialization library
// Copyright (c) 2011 Google Inc.
#[forbid(deprecated_mode)];
#[forbid(deprecated_pattern)];
#[forbid(non_camel_case_types)];

//! json serialization

use core::cmp::{Eq, Ord};
use result::{Result, Ok, Err};
use io::{WriterUtil, ReaderUtil};
use map::HashMap;
use map::Map;
use send_map::linear;
use sort::Sort;

/// Represents a json value
pub enum Json {
    Number(float),
    String(~str),
    Boolean(bool),
    List(List),
    Object(~Object),
    Null,
}

pub type List = ~[Json];
pub type Object = linear::LinearMap<~str, Json>;

pub struct Error {
    line: uint,
    col: uint,
    msg: @~str,
}

fn escape_str(s: &str) -> ~str {
    let mut escaped = ~"\"";
    for str::chars_each(s) |c| {
        match c {
          '"' => escaped += ~"\\\"",
          '\\' => escaped += ~"\\\\",
          '\x08' => escaped += ~"\\b",
          '\x0c' => escaped += ~"\\f",
          '\n' => escaped += ~"\\n",
          '\r' => escaped += ~"\\r",
          '\t' => escaped += ~"\\t",
          _ => escaped += str::from_char(c)
        }
    };

    escaped += ~"\"";

    escaped
}

fn spaces(n: uint) -> ~str {
    let mut ss = ~"";
    for n.times { str::push_str(&ss, " "); }
    return ss;
}

pub struct Serializer {
    priv wr: io::Writer,
}

pub fn Serializer(wr: io::Writer) -> Serializer {
    Serializer { wr: wr }
}

pub impl Serializer: serialization2::Serializer {
    fn emit_nil(&self) { self.wr.write_str("null") }

    fn emit_uint(&self, v: uint) { self.emit_float(v as float); }
    fn emit_u64(&self, v: u64) { self.emit_float(v as float); }
    fn emit_u32(&self, v: u32) { self.emit_float(v as float); }
    fn emit_u16(&self, v: u16) { self.emit_float(v as float); }
    fn emit_u8(&self, v: u8)   { self.emit_float(v as float); }

    fn emit_int(&self, v: int) { self.emit_float(v as float); }
    fn emit_i64(&self, v: i64) { self.emit_float(v as float); }
    fn emit_i32(&self, v: i32) { self.emit_float(v as float); }
    fn emit_i16(&self, v: i16) { self.emit_float(v as float); }
    fn emit_i8(&self, v: i8)   { self.emit_float(v as float); }

    fn emit_bool(&self, v: bool) {
        if v {
            self.wr.write_str("true");
        } else {
            self.wr.write_str("false");
        }
    }

    fn emit_f64(&self, v: f64) { self.emit_float(v as float); }
    fn emit_f32(&self, v: f32) { self.emit_float(v as float); }
    fn emit_float(&self, v: float) {
        self.wr.write_str(float::to_str(v, 6u));
    }

    fn emit_str(&self, v: &str) {
        let s = escape_str(v);
        self.wr.write_str(s);
    }

    fn emit_enum(&self, name: &str, f: fn()) {
        if name != "option" { fail ~"only supports option enum" }
        f()
    }
    fn emit_enum_variant(&self, _name: &str, id: uint, _cnt: uint, f: fn()) {
        if id == 0 {
            self.emit_nil();
        } else {
            f()
        }
    }
    fn emit_enum_variant_arg(&self, _idx: uint, f: fn()) {
        f()
    }

    fn emit_vec(&self, _len: uint, f: fn()) {
        self.wr.write_char('[');
        f();
        self.wr.write_char(']');
    }

    fn emit_vec_elt(&self, idx: uint, f: fn()) {
        if idx != 0 { self.wr.write_char(','); }
        f()
    }

    fn emit_box(&self, f: fn()) { f() }
    fn emit_uniq(&self, f: fn()) { f() }
    fn emit_rec(&self, f: fn()) {
        self.wr.write_char('{');
        f();
        self.wr.write_char('}');
    }
    fn emit_rec_field(&self, name: &str, idx: uint, f: fn()) {
        if idx != 0 { self.wr.write_char(','); }
        self.wr.write_str(escape_str(name));
        self.wr.write_char(':');
        f();
    }
    fn emit_tup(&self, sz: uint, f: fn()) {
        self.emit_vec(sz, f);
    }
    fn emit_tup_elt(&self, idx: uint, f: fn()) {
        self.emit_vec_elt(idx, f)
    }
}

pub struct PrettySerializer {
    priv wr: io::Writer,
    priv mut indent: uint,
}

pub fn PrettySerializer(wr: io::Writer) -> PrettySerializer {
    PrettySerializer { wr: wr, indent: 0 }
}

pub impl PrettySerializer: serialization2::Serializer {
    fn emit_nil(&self) { self.wr.write_str("null") }

    fn emit_uint(&self, v: uint) { self.emit_float(v as float); }
    fn emit_u64(&self, v: u64) { self.emit_float(v as float); }
    fn emit_u32(&self, v: u32) { self.emit_float(v as float); }
    fn emit_u16(&self, v: u16) { self.emit_float(v as float); }
    fn emit_u8(&self, v: u8)   { self.emit_float(v as float); }

    fn emit_int(&self, v: int) { self.emit_float(v as float); }
    fn emit_i64(&self, v: i64) { self.emit_float(v as float); }
    fn emit_i32(&self, v: i32) { self.emit_float(v as float); }
    fn emit_i16(&self, v: i16) { self.emit_float(v as float); }
    fn emit_i8(&self, v: i8)   { self.emit_float(v as float); }

    fn emit_bool(&self, v: bool) {
        if v {
            self.wr.write_str("true");
        } else {
            self.wr.write_str("false");
        }
    }

    fn emit_f64(&self, v: f64) { self.emit_float(v as float); }
    fn emit_f32(&self, v: f32) { self.emit_float(v as float); }
    fn emit_float(&self, v: float) {
        self.wr.write_str(float::to_str(v, 6u));
    }

    fn emit_str(&self, v: &str) { self.wr.write_str(escape_str(v)); }

    fn emit_enum(&self, name: &str, f: fn()) {
        if name != "option" { fail ~"only supports option enum" }
        f()
    }
    fn emit_enum_variant(&self, _name: &str, id: uint, _cnt: uint, f: fn()) {
        if id == 0 {
            self.emit_nil();
        } else {
            f()
        }
    }
    fn emit_enum_variant_arg(&self, _idx: uint, f: fn()) {
        f()
    }

    fn emit_vec(&self, _len: uint, f: fn()) {
        self.wr.write_char('[');
        self.indent += 2;
        f();
        self.indent -= 2;
        self.wr.write_char(']');
    }

    fn emit_vec_elt(&self, idx: uint, f: fn()) {
        if idx == 0 {
            self.wr.write_char('\n');
        } else {
            self.wr.write_str(",\n");
        }
        self.wr.write_str(spaces(self.indent));
        f()
    }

    fn emit_box(&self, f: fn()) { f() }
    fn emit_uniq(&self, f: fn()) { f() }
    fn emit_rec(&self, f: fn()) {
        self.wr.write_char('{');
        self.indent += 2;
        f();
        self.indent -= 2;
        self.wr.write_char('}');
    }
    fn emit_rec_field(&self, name: &str, idx: uint, f: fn()) {
        if idx == 0 {
            self.wr.write_char('\n');
        } else {
            self.wr.write_str(",\n");
        }
        self.wr.write_str(spaces(self.indent));
        self.wr.write_str(escape_str(name));
        self.wr.write_str(": ");
        f();
    }
    fn emit_tup(&self, sz: uint, f: fn()) {
        self.emit_vec(sz, f);
    }
    fn emit_tup_elt(&self, idx: uint, f: fn()) {
        self.emit_vec_elt(idx, f)
    }
}

pub fn to_serializer<S: serialization2::Serializer>(ser: &S, json: &Json) {
    match *json {
        Number(f) => ser.emit_float(f),
        String(s) => ser.emit_str(s),
        Boolean(b) => ser.emit_bool(b),
        List(v) => {
            do ser.emit_vec(v.len()) || {
                for v.eachi |i, elt| {
                    ser.emit_vec_elt(i, || to_serializer(ser, elt))
                }
            }
        }
        Object(o) => {
            do ser.emit_rec || {
                let mut idx = 0;
                for o.each |key, value| {
                    do ser.emit_rec_field(*key, idx) {
                        to_serializer(ser, value);
                    }
                    idx += 1;
                }
            }
        }
        Null => ser.emit_nil(),
    }
}

/// Serializes a json value into a io::writer
pub fn to_writer(wr: io::Writer, json: &Json) {
    to_serializer(&Serializer(wr), json)
}

/// Serializes a json value into a string
pub fn to_str(json: &Json) -> ~str {
    io::with_str_writer(|wr| to_writer(wr, json))
}

/// Serializes a json value into a io::writer
pub fn to_pretty_writer(wr: io::Writer, json: &Json) {
    to_serializer(&PrettySerializer(wr), json)
}

/// Serializes a json value into a string
pub fn to_pretty_str(json: &Json) -> ~str {
    io::with_str_writer(|wr| to_pretty_writer(wr, json))
}

pub struct Parser {
    priv rdr: io::Reader,
    priv mut ch: char,
    priv mut line: uint,
    priv mut col: uint,
}

/// Deserializes a json value from an io::reader
pub fn Parser(rdr: io::Reader) -> Parser {
    Parser {
        rdr: rdr,
        ch: rdr.read_char(),
        line: 1u,
        col: 1u,
    }
}

pub impl Parser {
    fn parse() -> Result<Json, Error> {
        match move self.parse_value() {
          Ok(move value) => {
            // Skip trailing whitespaces.
            self.parse_whitespace();
            // Make sure there is no trailing characters.
            if self.eof() {
                Ok(value)
            } else {
                self.error(~"trailing characters")
            }
          }
          Err(move e) => Err(e)
        }
    }
}

priv impl Parser {
    fn eof() -> bool { self.ch == -1 as char }

    fn bump() {
        self.ch = self.rdr.read_char();

        if self.ch == '\n' {
            self.line += 1u;
            self.col = 1u;
        } else {
            self.col += 1u;
        }
    }

    fn next_char() -> char {
        self.bump();
        self.ch
    }

    fn error<T>(+msg: ~str) -> Result<T, Error> {
        Err(Error { line: self.line, col: self.col, msg: @msg })
    }

    fn parse_value() -> Result<Json, Error> {
        self.parse_whitespace();

        if self.eof() { return self.error(~"EOF while parsing value"); }

        match self.ch {
          'n' => self.parse_ident(~"ull", Null),
          't' => self.parse_ident(~"rue", Boolean(true)),
          'f' => self.parse_ident(~"alse", Boolean(false)),
          '0' .. '9' | '-' => self.parse_number(),
          '"' =>
            match move self.parse_str() {
              Ok(move s) => Ok(String(s)),
              Err(move e) => Err(e),
            },
          '[' => self.parse_list(),
          '{' => self.parse_object(),
          _ => self.error(~"invalid syntax")
        }
    }

    fn parse_whitespace() {
        while char::is_whitespace(self.ch) { self.bump(); }
    }

    fn parse_ident(ident: ~str, +value: Json) -> Result<Json, Error> {
        if str::all(ident, |c| c == self.next_char()) {
            self.bump();
            Ok(move value)
        } else {
            self.error(~"invalid syntax")
        }
    }

    fn parse_number() -> Result<Json, Error> {
        let mut neg = 1f;

        if self.ch == '-' {
            self.bump();
            neg = -1f;
        }

        let mut res = match self.parse_integer() {
          Ok(res) => res,
          Err(e) => return Err(e)
        };

        if self.ch == '.' {
            match self.parse_decimal(res) {
              Ok(r) => res = r,
              Err(e) => return Err(e)
            }
        }

        if self.ch == 'e' || self.ch == 'E' {
            match self.parse_exponent(res) {
              Ok(r) => res = r,
              Err(e) => return Err(e)
            }
        }

        Ok(Number(neg * res))
    }

    fn parse_integer() -> Result<float, Error> {
        let mut res = 0f;

        match self.ch {
          '0' => {
            self.bump();

            // There can be only one leading '0'.
            match self.ch {
              '0' .. '9' => return self.error(~"invalid number"),
              _ => ()
            }
          }
          '1' .. '9' => {
            while !self.eof() {
                match self.ch {
                  '0' .. '9' => {
                    res *= 10f;
                    res += ((self.ch as int) - ('0' as int)) as float;

                    self.bump();
                  }
                  _ => break
                }
            }
          }
          _ => return self.error(~"invalid number")
        }

        Ok(res)
    }

    fn parse_decimal(res: float) -> Result<float, Error> {
        self.bump();

        // Make sure a digit follows the decimal place.
        match self.ch {
          '0' .. '9' => (),
          _ => return self.error(~"invalid number")
        }

        let mut res = res;
        let mut dec = 1f;
        while !self.eof() {
            match self.ch {
              '0' .. '9' => {
                dec /= 10f;
                res += (((self.ch as int) - ('0' as int)) as float) * dec;

                self.bump();
              }
              _ => break
            }
        }

        Ok(res)
    }

    fn parse_exponent(res: float) -> Result<float, Error> {
        self.bump();

        let mut res = res;
        let mut exp = 0u;
        let mut neg_exp = false;

        match self.ch {
          '+' => self.bump(),
          '-' => { self.bump(); neg_exp = true; }
          _ => ()
        }

        // Make sure a digit follows the exponent place.
        match self.ch {
          '0' .. '9' => (),
          _ => return self.error(~"invalid number")
        }

        while !self.eof() {
            match self.ch {
              '0' .. '9' => {
                exp *= 10u;
                exp += (self.ch as uint) - ('0' as uint);

                self.bump();
              }
              _ => break
            }
        }

        let exp = float::pow_with_uint(10u, exp);
        if neg_exp {
            res /= exp;
        } else {
            res *= exp;
        }

        Ok(res)
    }

    fn parse_str() -> Result<~str, Error> {
        let mut escape = false;
        let mut res = ~"";

        while !self.eof() {
            self.bump();

            if (escape) {
                match self.ch {
                  '"' => str::push_char(&res, '"'),
                  '\\' => str::push_char(&res, '\\'),
                  '/' => str::push_char(&res, '/'),
                  'b' => str::push_char(&res, '\x08'),
                  'f' => str::push_char(&res, '\x0c'),
                  'n' => str::push_char(&res, '\n'),
                  'r' => str::push_char(&res, '\r'),
                  't' => str::push_char(&res, '\t'),
                  'u' => {
                      // Parse \u1234.
                      let mut i = 0u;
                      let mut n = 0u;
                      while i < 4u {
                          match self.next_char() {
                            '0' .. '9' => {
                              n = n * 16u + (self.ch as uint)
                                          - ('0'     as uint);
                            },
                            'a' | 'A' => n = n * 16u + 10u,
                            'b' | 'B' => n = n * 16u + 11u,
                            'c' | 'C' => n = n * 16u + 12u,
                            'd' | 'D' => n = n * 16u + 13u,
                            'e' | 'E' => n = n * 16u + 14u,
                            'f' | 'F' => n = n * 16u + 15u,
                            _ => return self.error(
                                   ~"invalid \\u escape (unrecognized hex)")
                          }
                          i += 1u;
                      }

                      // Error out if we didn't parse 4 digits.
                      if i != 4u {
                          return self.error(
                            ~"invalid \\u escape (not four digits)");
                      }

                      str::push_char(&res, n as char);
                  }
                  _ => return self.error(~"invalid escape")
                }
                escape = false;
            } else if self.ch == '\\' {
                escape = true;
            } else {
                if self.ch == '"' {
                    self.bump();
                    return Ok(res);
                }
                str::push_char(&res, self.ch);
            }
        }

        self.error(~"EOF while parsing string")
    }

    fn parse_list() -> Result<Json, Error> {
        self.bump();
        self.parse_whitespace();

        let mut values = ~[];

        if self.ch == ']' {
            self.bump();
            return Ok(List(values));
        }

        loop {
            match move self.parse_value() {
              Ok(move v) => values.push(v),
              Err(move e) => return Err(e)
            }

            self.parse_whitespace();
            if self.eof() {
                return self.error(~"EOF while parsing list");
            }

            match self.ch {
              ',' => self.bump(),
              ']' => { self.bump(); return Ok(List(values)); }
              _ => return self.error(~"expected `,` or `]`")
            }
        };
    }

    fn parse_object() -> Result<Json, Error> {
        self.bump();
        self.parse_whitespace();

        let mut values = ~linear::LinearMap();

        if self.ch == '}' {
          self.bump();
          return Ok(Object(values));
        }

        while !self.eof() {
            self.parse_whitespace();

            if self.ch != '"' {
                return self.error(~"key must be a string");
            }

            let key = match move self.parse_str() {
              Ok(move key) => key,
              Err(move e) => return Err(e)
            };

            self.parse_whitespace();

            if self.ch != ':' {
                if self.eof() { break; }
                return self.error(~"expected `:`");
            }
            self.bump();

            match move self.parse_value() {
              Ok(move value) => { values.insert(key, value); }
              Err(move e) => return Err(e)
            }
            self.parse_whitespace();

            match self.ch {
              ',' => self.bump(),
              '}' => { self.bump(); return Ok(Object(values)); }
              _ => {
                  if self.eof() { break; }
                  return self.error(~"expected `,` or `}`");
              }
            }
        }

        return self.error(~"EOF while parsing object");
    }
}

/// Deserializes a json value from an io::reader
pub fn from_reader(rdr: io::Reader) -> Result<Json, Error> {
    Parser(rdr).parse()
}

/// Deserializes a json value from a string
pub fn from_str(s: &str) -> Result<Json, Error> {
    do io::with_str_reader(s) |rdr| {
        from_reader(rdr)
    }
}

pub struct Deserializer {
    priv json: Json,
    priv mut stack: ~[&Json],
}

pub fn Deserializer(rdr: io::Reader) -> Result<Deserializer, Error> {
    match move from_reader(rdr) {
        Ok(move json) => {
            let des = Deserializer { json: json, stack: ~[] };
            Ok(move des)
        }
        Err(move e) => Err(e)
    }
}

priv impl Deserializer {
    fn peek(&self) -> &self/Json {
        if self.stack.len() == 0 { self.stack.push(&self.json); }
        vec::last(self.stack)
    }

    fn pop(&self) -> &self/Json {
        if self.stack.len() == 0 { self.stack.push(&self.json); }
        vec::pop(self.stack)
    }
}

pub impl Deserializer: serialization2::Deserializer {
    fn read_nil(&self) -> () {
        debug!("read_nil");
        match *self.pop() {
            Null => (),
            _ => fail ~"not a null"
        }
    }

    fn read_u64(&self)  -> u64  { self.read_float() as u64 }
    fn read_u32(&self)  -> u32  { self.read_float() as u32 }
    fn read_u16(&self)  -> u16  { self.read_float() as u16 }
    fn read_u8 (&self)  -> u8   { self.read_float() as u8 }
    fn read_uint(&self) -> uint { self.read_float() as uint }

    fn read_i64(&self) -> i64 { self.read_float() as i64 }
    fn read_i32(&self) -> i32 { self.read_float() as i32 }
    fn read_i16(&self) -> i16 { self.read_float() as i16 }
    fn read_i8 (&self) -> i8  { self.read_float() as i8 }
    fn read_int(&self) -> int { self.read_float() as int }

    fn read_bool(&self) -> bool {
        debug!("read_bool");
        match *self.pop() {
            Boolean(b) => b,
            _ => fail ~"not a boolean"
        }
    }

    fn read_f64(&self) -> f64 { self.read_float() as f64 }
    fn read_f32(&self) -> f32 { self.read_float() as f32 }
    fn read_float(&self) -> float {
        debug!("read_float");
        match *self.pop() {
            Number(f) => f,
            _ => fail ~"not a number"
        }
    }

    fn read_str(&self) -> ~str {
        debug!("read_str");
        match *self.pop() {
            String(ref s) => copy *s,
            _ => fail ~"not a string"
        }
    }

    fn read_enum<T>(&self, name: ~str, f: fn() -> T) -> T {
        debug!("read_enum(%s)", name);
        if name != ~"option" { fail ~"only supports the option enum" }
        f()
    }

    fn read_enum_variant<T>(&self, f: fn(uint) -> T) -> T {
        debug!("read_enum_variant()");
        let idx = match *self.peek() {
            Null => 0,
            _ => 1,
        };
        f(idx)
    }

    fn read_enum_variant_arg<T>(&self, idx: uint, f: fn() -> T) -> T {
        debug!("read_enum_variant_arg(idx=%u)", idx);
        if idx != 0 { fail ~"unknown index" }
        f()
    }

    fn read_vec<T>(&self, f: fn(uint) -> T) -> T {
        debug!("read_vec()");
        let len = match *self.peek() {
            List(ref list) => list.len(),
            _ => fail ~"not a list",
        };
        let res = f(len);
        self.pop();
        res
    }

    fn read_vec_elt<T>(&self, idx: uint, f: fn() -> T) -> T {
        debug!("read_vec_elt(idx=%u)", idx);
        match *self.peek() {
            List(ref list) => {
                // FIXME(#3148)---should be inferred
                let list: &self/~[Json] = list;

                self.stack.push(&list[idx]);
                f()
            }
            _ => fail ~"not a list",
        }
    }

    fn read_box<T>(&self, f: fn() -> T) -> T {
        debug!("read_box()");
        f()
    }

    fn read_uniq<T>(&self, f: fn() -> T) -> T {
        debug!("read_uniq()");
        f()
    }

    fn read_rec<T>(&self, f: fn() -> T) -> T {
        debug!("read_rec()");
        let value = f();
        self.pop();
        value
    }

    fn read_rec_field<T>(&self, f_name: ~str, f_idx: uint,
                         f: fn() -> T) -> T {
        debug!("read_rec_field(%s, idx=%u)", f_name, f_idx);
        let top = self.peek();
        match *top {
            Object(ref obj) => {
                // FIXME(#3148) This hint should not be necessary.
                let obj: &self/~Object = obj;

                match obj.find_ref(&f_name) {
                    None => fail fmt!("no such field: %s", f_name),
                    Some(json) => {
                        self.stack.push(json);
                        f()
                    }
                }
            }
            Number(_) => fail ~"num",
            String(_) => fail ~"str",
            Boolean(_) => fail ~"bool",
            List(_) => fail fmt!("list: %?", top),
            Null => fail ~"null",

            //_ => fail fmt!("not an object: %?", *top)
        }
    }

    fn read_tup<T>(&self, sz: uint, f: fn() -> T) -> T {
        debug!("read_tup(sz=%u)", sz);
        let value = f();
        self.pop();
        value
    }

    fn read_tup_elt<T>(&self, idx: uint, f: fn() -> T) -> T {
        debug!("read_tup_elt(idx=%u)", idx);
        match *self.peek() {
            List(ref list) => {
                // FIXME(#3148)---should be inferred
                let list: &self/~[Json] = list;
                self.stack.push(&list[idx]);
                f()
            }
            _ => fail ~"not a list"
        }
    }
}

impl Json : Eq {
    pure fn eq(other: &Json) -> bool {
        // XXX: This is ugly because matching on references is broken, and
        // we can't match on dereferenced tuples without a copy.
        match self {
            Number(f0) =>
                match *other { Number(f1) => f0 == f1, _ => false },
            String(s0) =>
                match *other { String(s1) => s0 == s1, _ => false },
            Boolean(b0) =>
                match *other { Boolean(b1) => b0 == b1, _ => false },
            Null =>
                match *other { Null => true, _ => false },
            List(v0) =>
                match *other { List(v1) => v0 == v1, _ => false },
            Object(ref d0) => {
                match *other {
                    Object(ref d1) => {
                        if d0.len() == d1.len() {
                            let mut equal = true;
                            for d0.each |k, v0| {
                                match d1.find_ref(k) {
                                    Some(v1) if v0 == v1 => { },
                                    _ => { equal = false; break }
                                }
                            };
                            equal
                        } else {
                            false
                        }
                    }
                    _ => false
                }
            }
        }
    }
    pure fn ne(other: &Json) -> bool { !self.eq(other) }
}

/// Test if two json values are less than one another
impl Json : Ord {
    pure fn lt(other: &Json) -> bool {
        match self {
            Number(f0) => {
                match *other {
                    Number(f1) => f0 < f1,
                    String(_) | Boolean(_) | List(_) | Object(_) |
                    Null => true
                }
            }

            String(s0) => {
                match *other {
                    Number(_) => false,
                    String(s1) => s0 < s1,
                    Boolean(_) | List(_) | Object(_) | Null => true
                }
            }

            Boolean(b0) => {
                match *other {
                    Number(_) | String(_) => false,
                    Boolean(b1) => b0 < b1,
                    List(_) | Object(_) | Null => true
                }
            }

            List(l0) => {
                match *other {
                    Number(_) | String(_) | Boolean(_) => false,
                    List(l1) => l0 < l1,
                    Object(_) | Null => true
                }
            }

            Object(d0) => {
                match *other {
                    Number(_) | String(_) | Boolean(_) | List(_) => false,
                    Object(d1) => {
                        unsafe {
                            let mut d0_flat = ~[];
                            let mut d1_flat = ~[];

                            // XXX: this is horribly inefficient...
                            for d0.each |k, v| {
                                 d0_flat.push((@copy *k, @copy *v));
                            }
                            d0_flat.qsort();

                            for d1.each |k, v| {
                                d1_flat.push((@copy *k, @copy *v));
                            }
                            d1_flat.qsort();

                            d0_flat < d1_flat
                        }
                    }
                    Null => true
                }
            }

            Null => {
                match *other {
                    Number(_) | String(_) | Boolean(_) | List(_) |
                    Object(_) =>
                        false,
                    Null => true
                }
            }
        }
    }
    pure fn le(other: &Json) -> bool { !(*other).lt(&self) }
    pure fn ge(other: &Json) -> bool { !self.lt(other) }
    pure fn gt(other: &Json) -> bool { (*other).lt(&self)  }
}

impl Error : Eq {
    pure fn eq(other: &Error) -> bool {
        self.line == other.line &&
        self.col == other.col &&
        self.msg == other.msg
    }
    pure fn ne(other: &Error) -> bool { !self.eq(other) }
}

trait ToJson { fn to_json() -> Json; }

impl Json: ToJson {
    fn to_json() -> Json { copy self }
}

impl @Json: ToJson {
    fn to_json() -> Json { (*self).to_json() }
}

impl int: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl i8: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl i16: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl i32: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl i64: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl uint: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl u8: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl u16: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl u32: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl u64: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl float: ToJson {
    fn to_json() -> Json { Number(self) }
}

impl f32: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl f64: ToJson {
    fn to_json() -> Json { Number(self as float) }
}

impl (): ToJson {
    fn to_json() -> Json { Null }
}

impl bool: ToJson {
    fn to_json() -> Json { Boolean(self) }
}

impl ~str: ToJson {
    fn to_json() -> Json { String(copy self) }
}

impl @~str: ToJson {
    fn to_json() -> Json { String(copy *self) }
}

impl <A: ToJson, B: ToJson> (A, B): ToJson {
    fn to_json() -> Json {
        match self {
          (a, b) => {
            List(~[a.to_json(), b.to_json()])
          }
        }
    }
}

impl <A: ToJson, B: ToJson, C: ToJson> (A, B, C): ToJson {
    fn to_json() -> Json {
        match self {
          (a, b, c) => {
            List(~[a.to_json(), b.to_json(), c.to_json()])
          }
        }
    }
}

impl <A: ToJson> ~[A]: ToJson {
    fn to_json() -> Json { List(self.map(|elt| elt.to_json())) }
}

impl <A: ToJson Copy> linear::LinearMap<~str, A>: ToJson {
    fn to_json() -> Json {
        let mut d = linear::LinearMap();
        for self.each() |key, value| {
            d.insert(copy *key, value.to_json());
        }
        Object(~d)
    }
}

/*
impl <A: ToJson Copy> @std::map::HashMap<~str, A>: ToJson {
    fn to_json() -> Json {
        let mut d = linear::LinearMap();
        for self.each_ref |key, value| {
            d.insert(copy *key, value.to_json());
        }
        Object(~d)
    }
}
*/

impl <A: ToJson> Option<A>: ToJson {
    fn to_json() -> Json {
        match self {
          None => Null,
          Some(value) => value.to_json()
        }
    }
}

impl Json: to_str::ToStr {
    fn to_str() -> ~str { to_str(&self) }
}

impl Error: to_str::ToStr {
    fn to_str() -> ~str {
        fmt!("%u:%u: %s", self.line, self.col, *self.msg)
    }
}

#[cfg(test)]
mod tests {
    fn mk_object(items: &[(~str, Json)]) -> Json {
        let mut d = ~linear::LinearMap();

        for items.each |item| {
            match *item {
                (key, value) => { d.insert(copy key, copy value); },
            }
        };

        Object(d)
    }

    #[test]
    fn test_write_null() {
        assert to_str(&Null) == ~"null";
    }

    #[test]
    fn test_write_number() {
        assert to_str(&Number(3f)) == ~"3";
        assert to_str(&Number(3.1f)) == ~"3.1";
        assert to_str(&Number(-1.5f)) == ~"-1.5";
        assert to_str(&Number(0.5f)) == ~"0.5";
    }

    #[test]
    fn test_write_str() {
        assert to_str(&String(~"")) == ~"\"\"";
        assert to_str(&String(~"foo")) == ~"\"foo\"";
    }

    #[test]
    fn test_write_bool() {
        assert to_str(&Boolean(true)) == ~"true";
        assert to_str(&Boolean(false)) == ~"false";
    }

    #[test]
    fn test_write_list() {
        assert to_str(&List(~[])) == ~"[]";
        assert to_str(&List(~[Boolean(true)])) == ~"[true]";
        assert to_str(&List(~[
            Boolean(false),
            Null,
            List(~[String(~"foo\nbar"), Number(3.5f)])
        ])) == ~"[false,null,[\"foo\\nbar\",3.5]]";
    }

    #[test]
    fn test_write_object() {
        assert to_str(&mk_object(~[])) == ~"{}";
        assert to_str(&mk_object(~[(~"a", Boolean(true))]))
            == ~"{\"a\":true}";
        let a = mk_object(~[
            (~"a", Boolean(true)),
            (~"b", List(~[
                mk_object(~[(~"c", String(~"\x0c\r"))]),
                mk_object(~[(~"d", String(~""))])
            ]))
        ]);
        // We can't compare the strings directly because the object fields be
        // printed in a different order.
        let b = result::unwrap(from_str(to_str(&a)));
        assert a == b;
    }

    #[test]
    fn test_trailing_characters() {
        assert from_str(~"nulla") ==
            Err(Error {line: 1u, col: 5u, msg: @~"trailing characters"});
        assert from_str(~"truea") ==
            Err(Error {line: 1u, col: 5u, msg: @~"trailing characters"});
        assert from_str(~"falsea") ==
            Err(Error {line: 1u, col: 6u, msg: @~"trailing characters"});
        assert from_str(~"1a") ==
            Err(Error {line: 1u, col: 2u, msg: @~"trailing characters"});
        assert from_str(~"[]a") ==
            Err(Error {line: 1u, col: 3u, msg: @~"trailing characters"});
        assert from_str(~"{}a") ==
            Err(Error {line: 1u, col: 3u, msg: @~"trailing characters"});
    }

    #[test]
    fn test_read_identifiers() {
        assert from_str(~"n") ==
            Err(Error {line: 1u, col: 2u, msg: @~"invalid syntax"});
        assert from_str(~"nul") ==
            Err(Error {line: 1u, col: 4u, msg: @~"invalid syntax"});

        assert from_str(~"t") ==
            Err(Error {line: 1u, col: 2u, msg: @~"invalid syntax"});
        assert from_str(~"truz") ==
            Err(Error {line: 1u, col: 4u, msg: @~"invalid syntax"});

        assert from_str(~"f") ==
            Err(Error {line: 1u, col: 2u, msg: @~"invalid syntax"});
        assert from_str(~"faz") ==
            Err(Error {line: 1u, col: 3u, msg: @~"invalid syntax"});

        assert from_str(~"null") == Ok(Null);
        assert from_str(~"true") == Ok(Boolean(true));
        assert from_str(~"false") == Ok(Boolean(false));
        assert from_str(~" null ") == Ok(Null);
        assert from_str(~" true ") == Ok(Boolean(true));
        assert from_str(~" false ") == Ok(Boolean(false));
    }

    #[test]
    fn test_read_number() {
        assert from_str(~"+") ==
            Err(Error {line: 1u, col: 1u, msg: @~"invalid syntax"});
        assert from_str(~".") ==
            Err(Error {line: 1u, col: 1u, msg: @~"invalid syntax"});

        assert from_str(~"-") ==
            Err(Error {line: 1u, col: 2u, msg: @~"invalid number"});
        assert from_str(~"00") ==
            Err(Error {line: 1u, col: 2u, msg: @~"invalid number"});
        assert from_str(~"1.") ==
            Err(Error {line: 1u, col: 3u, msg: @~"invalid number"});
        assert from_str(~"1e") ==
            Err(Error {line: 1u, col: 3u, msg: @~"invalid number"});
        assert from_str(~"1e+") ==
            Err(Error {line: 1u, col: 4u, msg: @~"invalid number"});

        assert from_str(~"3") == Ok(Number(3f));
        assert from_str(~"3.1") == Ok(Number(3.1f));
        assert from_str(~"-1.2") == Ok(Number(-1.2f));
        assert from_str(~"0.4") == Ok(Number(0.4f));
        assert from_str(~"0.4e5") == Ok(Number(0.4e5f));
        assert from_str(~"0.4e+15") == Ok(Number(0.4e15f));
        assert from_str(~"0.4e-01") == Ok(Number(0.4e-01f));
        assert from_str(~" 3 ") == Ok(Number(3f));
    }

    #[test]
    fn test_read_str() {
        assert from_str(~"\"") ==
            Err(Error {line: 1u, col: 2u, msg: @~"EOF while parsing string"});
        assert from_str(~"\"lol") ==
            Err(Error {line: 1u, col: 5u, msg: @~"EOF while parsing string"});

        assert from_str(~"\"\"") == Ok(String(~""));
        assert from_str(~"\"foo\"") == Ok(String(~"foo"));
        assert from_str(~"\"\\\"\"") == Ok(String(~"\""));
        assert from_str(~"\"\\b\"") == Ok(String(~"\x08"));
        assert from_str(~"\"\\n\"") == Ok(String(~"\n"));
        assert from_str(~"\"\\r\"") == Ok(String(~"\r"));
        assert from_str(~"\"\\t\"") == Ok(String(~"\t"));
        assert from_str(~" \"foo\" ") == Ok(String(~"foo"));
    }

    #[test]
    fn test_unicode_hex_escapes_in_str() {
        assert from_str(~"\"\\u12ab\"") == Ok(String(~"\u12ab"));
        assert from_str(~"\"\\uAB12\"") == Ok(String(~"\uAB12"));
    }

    #[test]
    fn test_read_list() {
        assert from_str(~"[") ==
            Err(Error {line: 1u, col: 2u, msg: @~"EOF while parsing value"});
        assert from_str(~"[1") ==
            Err(Error {line: 1u, col: 3u, msg: @~"EOF while parsing list"});
        assert from_str(~"[1,") ==
            Err(Error {line: 1u, col: 4u, msg: @~"EOF while parsing value"});
        assert from_str(~"[1,]") ==
            Err(Error {line: 1u, col: 4u, msg: @~"invalid syntax"});
        assert from_str(~"[6 7]") ==
            Err(Error {line: 1u, col: 4u, msg: @~"expected `,` or `]`"});

        assert from_str(~"[]") == Ok(List(~[]));
        assert from_str(~"[ ]") == Ok(List(~[]));
        assert from_str(~"[true]") == Ok(List(~[Boolean(true)]));
        assert from_str(~"[ false ]") == Ok(List(~[Boolean(false)]));
        assert from_str(~"[null]") == Ok(List(~[Null]));
        assert from_str(~"[3, 1]") == Ok(List(~[Number(3f), Number(1f)]));
        assert from_str(~"\n[3, 2]\n") == Ok(List(~[Number(3f), Number(2f)]));
        assert from_str(~"[2, [4, 1]]") ==
               Ok(List(~[Number(2f), List(~[Number(4f), Number(1f)])]));
    }

    #[test]
    fn test_read_object() {
        assert from_str(~"{") ==
            Err(Error {line: 1u, col: 2u, msg: @~"EOF while parsing object"});
        assert from_str(~"{ ") ==
            Err(Error {line: 1u, col: 3u, msg: @~"EOF while parsing object"});
        assert from_str(~"{1") ==
            Err(Error {line: 1u, col: 2u, msg: @~"key must be a string"});
        assert from_str(~"{ \"a\"") ==
            Err(Error {line: 1u, col: 6u, msg: @~"EOF while parsing object"});
        assert from_str(~"{\"a\"") ==
            Err(Error {line: 1u, col: 5u, msg: @~"EOF while parsing object"});
        assert from_str(~"{\"a\" ") ==
            Err(Error {line: 1u, col: 6u, msg: @~"EOF while parsing object"});

        assert from_str(~"{\"a\" 1") ==
            Err(Error {line: 1u, col: 6u, msg: @~"expected `:`"});
        assert from_str(~"{\"a\":") ==
            Err(Error {line: 1u, col: 6u, msg: @~"EOF while parsing value"});
        assert from_str(~"{\"a\":1") ==
            Err(Error {line: 1u, col: 7u, msg: @~"EOF while parsing object"});
        assert from_str(~"{\"a\":1 1") ==
            Err(Error {line: 1u, col: 8u, msg: @~"expected `,` or `}`"});
        assert from_str(~"{\"a\":1,") ==
            Err(Error {line: 1u, col: 8u, msg: @~"EOF while parsing object"});

        assert result::unwrap(from_str(~"{}")) == mk_object(~[]);
        assert result::unwrap(from_str(~"{\"a\": 3}")) ==
                  mk_object(~[(~"a", Number(3.0f))]);

        assert result::unwrap(from_str(~"{ \"a\": null, \"b\" : true }")) ==
                  mk_object(~[
                      (~"a", Null),
                      (~"b", Boolean(true))]);
        assert result::unwrap(
                      from_str(~"\n{ \"a\": null, \"b\" : true }\n")) ==
                  mk_object(~[
                      (~"a", Null),
                      (~"b", Boolean(true))]);
        assert result::unwrap(from_str(~"{\"a\" : 1.0 ,\"b\": [ true ]}")) ==
                  mk_object(~[
                      (~"a", Number(1.0)),
                      (~"b", List(~[Boolean(true)]))
                  ]);
        assert result::unwrap(from_str(
                      ~"{" +
                          ~"\"a\": 1.0, " +
                          ~"\"b\": [" +
                              ~"true," +
                              ~"\"foo\\nbar\", " +
                              ~"{ \"c\": {\"d\": null} } " +
                          ~"]" +
                      ~"}")) ==
                  mk_object(~[
                      (~"a", Number(1.0f)),
                      (~"b", List(~[
                          Boolean(true),
                          String(~"foo\nbar"),
                          mk_object(~[
                              (~"c", mk_object(~[(~"d", Null)]))
                          ])
                      ]))
                  ]);
    }

    #[test]
    fn test_multiline_errors() {
        assert from_str(~"{\n  \"foo\":\n \"bar\"") ==
            Err(Error {line: 3u, col: 8u, msg: @~"EOF while parsing object"});
    }
}