/**
 * @package de.atwillys.cc.swl
 * @license BSD (simplified)
 * @author Stefan Wilhelm (stfwi)
 *
 * @json.hh
 * @ccflags
 * @ldflags
 * @platform linux, bsd, windows
 * @standard >= c++98
 *
 * -----------------------------------------------------------------------------
 *
 * JSON parser / composer class template. Requires variable type class
 * `sw::detail::basic_var<...>` / `sw::var`.
 *
 *  namespace sw { namespace detail {
 *    template <typename string_typeype> class basic_json;
 *  }}
 *
 * Default specialisation with std::string:
 *
 *  namespace sw {
 *    typedef detail::basic_json<std::string> json;
 *  }
 *
 * -----------------------------------------------------------------------------
 *
 * Brief features and annotations
 *
 *  - parser, composer.
 *  - Strict/non-strict parsing/composing (see below)
 *  - Understands unicode escapes, converts latter to utf8
 *  - Understands single line comments: `// COMMENTS <newline>`
 *  - Understands multi line comments: `/ * COMMENTS  * /`
 *  - Throws understandable exceptions with error line/colum.
 *
 *  - The 'document structure' is not saved, parse and re-compose can have
 *    different output. The data, however, are identical.
 *  - Comments are generally removed.
 *  - Parsed unicode escape sequences will be composed as UTF8.
 *  - Always composed in compressed form (no newlines, no spaces).
 *
 *    --> Use this class for reading (e.g. config files) and data exchange,
 *        not for modifying human readable JSON 'documents'.
 *
 *  - Does not work with compiler option `-fno-exceptions`, but with `-fno-rtti`.
 *
 * -----------------------------------------------------------------------------
 *
 * The main functions used are static and named `parse(...)` and `compose(...)`.
 * `parse()` can take either a `istream` reference or a const `string` reference,
 * `compose()` can either write to a `ostream` or return a `string`.
 *
 * As additional argument, options can be passed to the parser/composer, where
 * currently the only options are `o_no` (no options) and `o_strict`, which
 * means
 *
 *      - `o_strict`: The parser shall not try to "overlook" inconsistencies
 *                    but throw on everything that could mean trouble.
 *
 *      - `o_strict`: The composer must apply strict rules, means e.g. it must
 *                    quote object keys, even if they are compliant to alphanumeric
 *                    variable name conventions ( `{ "a":10 }`, NOT {a:10} ).
 *
 * The parser is non-strict by default, the composer is strict by default.
 *
 * Usage:
 *
 *  - Parse:
 *
 *     sw::var result = sw::json::parse(stream, (<options>));
 *
 *     sw::var result = sw::json::parse(string, (<options>));
 *
 *    e.g.:
 *
 *      sw::var r = sw::json::parse(cin); // strict is optional
 *      r.dump(cerr);
 *
 * - Compose:
 *
 *    sw::json::compose((const sw::var&) what, (ostream&) where); // --> ostream
 *
 *    string result = sw::json::compose((const sw::var&) what);   // --> string
 *
 * -----------------------------------------------------------------------------
 * +++ BSD license header (You know that ...) +++
 * Copyright (c) 2010-2014, Stefan Wilhelm (stfwi, <cerbero s@atwilly s.de>)
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met: (1) Redistributions
 * of source code must retain the above copyright notice, this list of conditions
 * and the following disclaimer. (2) Redistributions in binary form must reproduce
 * the above copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the distribution.
 * (3) Neither the name of atwillys.de nor the names of its contributors may be
 * used to endorse or promote products derived from this software without specific
 * prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS
 * AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 * -----------------------------------------------------------------------------
 */
#ifndef SW__JSON_HH
#define SW__JSON_HH

#include "var.hh"
#include <string>
#include <cctype>
#include <iostream>
#include <vector>
#include <stack>
#include <stdexcept>
#include <algorithm>

namespace sw { namespace detail {

template <typename StringType>
class basic_json
{

  //////////////////////////////////////////////////////////////////////////////
  // Types

public:

  typedef StringType string_type;
  typedef typename string_type::value_type char_type; // Char type
  typedef unsigned int ucchar_t; // Unicode character type, >= uint16
  typedef std::basic_istream<char_type> istream_type;
  typedef std::basic_ostream<char_type> ostream_type;
  typedef std::basic_stringstream<char_type> sstream_type;
  typedef basic_var<string_type, typename sw::var::float_type, typename sw::var::int_type> var_type;
  typedef std::runtime_error exception_type;
  typedef enum { o_no=0, o_strict } options_type;

  //////////////////////////////////////////////////////////////////////////////
  // Static "main functions"

public:

  /**
   * Parses a JSON text stream into an sw::var variable.
   * @param istream_type& stream
   * @param bool strict=false
   * @return var_type
   */
  static inline var_type parse(istream_type& stream, bool strict=false)
  { var_type r; basic_json()(stream, r, strict ? o_strict:o_no); return r; }

  /**
   * Parses a JSON text into an sw::var variable.
   * @param const string_type& text
   * @param bool strict=false
   * @return var_type
   */
  static inline var_type parse(const string_type& txt, bool strict=false)
  { var_type r; sstream_type s(txt); basic_json()(s, r, strict ? o_strict:o_no ); return r; }

  /**
   * Composes JSON to a given stream. Note that comments are omitted and the
   * order of object key-value pairs can differ from a JSON string parsed
   * before.
   * @param const var_type& v
   * @param ostream_type& stream
   * @param options_type opts = o_strict
   * @return ostream_type& stream
   */
  static inline ostream_type& compose(const var_type& v, ostream_type& stream, options_type opts=o_strict)
  { basic_json()(v, stream, opts); return stream; }

  /**
   * Composes JSON to a given string. Note that comments are omitted and the
   * order of object key-value pairs can differ from a JSON string parsed
   * before.
   * @param const var_type& v
   * @param ostream_type& stream
   * @param options_type opts = o_strict
   * @return ostream_type& stream
   */
  static inline string_type compose(const var_type& v, options_type opts=o_strict)
  { sstream_type s; basic_json()(v, s, opts); return s.str(); }


  //////////////////////////////////////////////////////////////////////////////
  // Construction / destruction

public:

  /**
   * Default constructor
   */
  inline basic_json() :
    is_(NULL), os_(NULL), line_(1), line_pos_(1), eof_overread_('\n'), opts_(o_no)
  { ; }

  /**
   * Destructor
   */
  virtual ~basic_json()
  { ; }

  //////////////////////////////////////////////////////////////////////////////
  // "Main methods" exposed as operator (), getters.

public:

  /**
   * Parses a JSON text stream into an sw::var variable.
   * @param istream_type& stream
   * @param bool strict=false
   * @param var_type& result
   * @return var_type&
   */
  inline var_type& operator() (istream_type& stream, var_type& result, options_type opts=o_no)
  { is_ = &stream; opts_=opts; parse_root(result); return result; }

  /**
   * Composes JSON to a given stream. Note that comments are omitted and the
   * order of object key-value pairs can differ from a JSON string parsed
   * before.
   * @param const var_type& v
   * @param ostream_type& stream
   * @param options_type opts = o_strict
   * @return ostream_type& stream
   */
  inline ostream_type& operator() (const var_type& v, ostream_type& stream, options_type opts=o_strict)
  { os_ = &stream; opts_=opts; compose_root(v); return stream; }

  /**
   * True if strict parsing/composing.
   * @return bool
   */
  inline bool strict() const
  { return (opts_ & o_strict) == o_strict; }


  //////////////////////////////////////////////////////////////////////////////
  // Parse

protected:

  inline bool eof() const
  { return is_->eof(); }

  /**
   * Get next char from stream. (_is must be assigned!). Throw exception
   * on bad stream. Returns 0 on EOF.
   * @return ch_t
   */
  inline char_type get()
  {
    char_type c;
    if(!is_->get(c)) {
      if(!is_->eof()) {
        throw exception_type("Read error");
      } else if(eof_overread_ != '\0') {
        // We accept one char overread before throwing.
        c = '\0'; eof_overread_ = '\0';
      } else {
        throw exception_type("Unexpected end of input");
      }
    } else {
      if(c == '\n') { line_++; line_pos_=0; }
      line_pos_++;
    }
    return c;
  }

  /**
   * Take a glance at the next character without pulling it out of the stream.
   * @return char_type
   */
  inline char_type peek() const
  { char_type c=is_->peek(); return (c==istream_type::traits_type::eof()) ? 0:c; }

  /**
   * Put a character back into the stream. Decrements position but does not
   * unwrap line counter.
   * @param char_type c
   */
  inline void putback(char_type c)
  { if(c) { line_pos_--; is_->putback(c); } }

  /**
   * Skips spaces
   */
  inline void skip_spaces()
  { while(is_->good() && std::isspace(peek()) && get()); }


  /**
   * Detects // and / * * / comments and skips them.
   */
  void skip_comments()
  {
    // Could be multiple comments joined, eventually get() will force abort
    // on eof().
    while(!eof()) {
      skip_spaces();
      if(peek() != '/') return;
      char_type c = get();
      char_type c1 = peek();
      if((c1 != '/') && (c1 != '*')) { putback(c); return; }
      if(c1 == '/') {
        while((c=get()) && c!='\n' && c!='\r');
        if(eof()) { eof_overread_ = '\n'; return; }
      } else {
        while((c=get()) && !(c=='*' && peek()=='/'));
        get();
      }
    }
  }

  /**
   * Starting point of the whole parse process
   * @param var_type &node
   */
  void parse_root(var_type &node)
  {
    try {
      eof_overread_ = '\n';
      line_ = 1;
      line_pos_ = 1;
      node.clear();
      if(!is_) throw exception_type("Input stream pointer is NULL. Can't parse.");
      skip_comments();
      if(eof()) return; // Empty input --> var will be `unset`.
      parse_any(node);
      skip_comments();
      if(!eof()) throw exception_type("End of input expected");
    } catch(const exception_type &e) {
      try { node.clear(); } catch(...) { ; }
      sstream_type ss; ss << "JSON parser [@" << line_ << ":" << line_pos_ << "]: " << e.what();
      throw exception_type(ss.str());
    }
  }

  /**
   * Relay for parsing others.
   * @param var_type &node
   */
  void parse_any(var_type &node)
  {
    skip_comments();
    char_type c = get();

    if(c == '"') {
      parse_string(node);
    } else if(c == '[') {
      parse_array(node);
    } else if(c == '{') {
      parse_object(node);
    } else if(std::isdigit(c) || c=='-' || c=='+' || c=='.') {
      putback(c); parse_number(node);
    } else if(std::isalpha(c) || c=='_') {
      putback(c); parse_literal(node);
    } else if(c != 0) {
      throw exception_type(string_type("Unexpected character '")+c+"'");
    } else {
      node.clear();
    }
  }

  /**
   * Parses a number, assigns either int or floating point value to the node.
   * Throws on error.
   * @param var_type &node
   */
  void parse_number(var_type &node)
  {
    sstream_type ss;
    char_type c;
    bool is_float = false;
    if(peek() == '+') get();
    while((c = get())) {
      if(std::isdigit(c)) {
        ss << c;
      } else if(c=='.' || c=='e' || c=='E' || c=='+' || c=='-') {
        ss << c;
        is_float = true;
      } else {
        putback(c);
        break;
      }
    }
    double d;
    string_type s = ss.str();
    if(!(ss >> d) || !ss.eof()) { // Expected: Whole string is the number
      node.f(std::numeric_limits<double>::quiet_NaN());
      throw exception_type(string_type("Invalid numeric expression: '")+s+"'");
    } else if(is_float) {
      node.f(d);
    } else {
      node.i((typename var_type::int_type)d);
    }
  }

  /**
   * Parse known literals (case insensitively). Throw on error.
   * @param var_type &node
   */
  void parse_literal(var_type &node)
  {
    char_type c = get();
    if(!std::isalpha(c) && c != '_') {
      throw exception_type("Bug: Can't parse a literal not starting with an `alnum`!");
    }
    std::string s;
    s.reserve(16);
    s += c;
    while((c = get()) && (std::isalnum(c) || c=='_')) s += c;
    putback(c);
    std::string ls(s);
    std::transform(s.begin(), s.end(), s.begin(), ::tolower);
    if(s == "null") {
      node = var_type::nul();
    } else if(s == "false") {
      node.b(false);
    } else if(s == "true") {
      node.b(true);
    } else if(!strict() && s == "undefined") {
      node.clear();
    } else {
      throw exception_type(string_type("Unknown literal '") + ls + "'");
    }
  }

  /**
   * Parse array. Expected that the leading '[' literal is already shifted off.
   * Throws on error.
   * @param var_type &node
   */
  void parse_array(var_type &node)
  {
    node.v(var_type::empty_vector());
    skip_comments();
    if(peek() == ']') { get(); return; }
    while(true) {
      var_type v;
      parse_any(v);
      node.push_back(v);
      skip_comments();
      char_type c = get();
      if(c == ']') break;
      if(c != ',') throw exception_type("Expected ']' or ',' while parsing array");
    }
  }

  /**
   * Parse object. Expected that the leading '{' literal is already shifted off.
   * Throws on error.
   * @param var_type &node
   */
  void parse_object(var_type &node)
  {
    node.m(var_type::empty_map());
    skip_comments();
    if(peek() == '}') { get(); return; }
    while(true) {
      string_type key = parse_object_key();
      skip_comments();
      if(get() != ':') throw exception_type("Missing ':' after object key");
      var_type v;
      parse_any(v);
      node.m(key, v);
      skip_comments();
      char_type c = get();
      if(c == '}') break;
      if(c != ',') throw exception_type("Expected '}' or ',' while parsing object");
    }
  }

  /**
   *
   * @return
   */
  string_type parse_object_key()
  {
    skip_comments();
    char c = get();
    if(c == '"') {
      var_type v;
      parse_string(v);
      return v.s();
    } else if(std::isalpha(c) || c=='_' || (!strict() && std::isdigit(c))) {
      string_type s; s.reserve(32);
      s += c;
      while((c=get()) && (std::isalnum(c) || c=='_')) s += c;
      if(!std::isspace(c)) putback(c);
      return s;
    } else {
      throw exception_type(string_type("Invalid object key start character '")+c+"'");
    }
  }

  /**
   * Parse string. Expected that the beginning literal is already shifted off
   * the stream.
   * @param var_type &node
   */
  void parse_string(var_type &node)
  {
    sstream_type ss;
    char_type c;
    while((c = get())) {
      switch(c) {
        case '"':
          node.s(ss.str());
          return;
          break;
        case '\\':
          switch(peek()) {
            case '\\':
            case '"' :
            case '/' : ss << get(); break;
            case 'n' : ss << "\n"; get(); break;
            case 'r' : ss << "\r"; get(); break;
            case 't' : ss << "\t"; get(); break;
            case 'u' : putback(c); ss << parse_unicode_escape_to_utf8(); break;
            case 'v' : ss << "\v"; get(); break;
            case 'f' : ss << "\f"; get(); break;
            case 'b' : ss << "\b"; get(); break;
            case 'a' : ss << "\a"; get(); break;
            default  :
              if(!strict()) {
                ss << '\\';
              } else {
                throw exception_type(string_type("Unexpected escape character '\\")+c+"'");
              }
          }
          break;
        default:
          ss << c;
      }
    }
    throw exception_type("Unexpected end of file while parsing string.");
  }

  /**
   * Returns utf8 string from one or more (concatenated) unicode escape
   * sequences.
   * @return string_type
   */
  string_type parse_unicode_escape_to_utf8()
  {
    string_type s; s.reserve(8);
    while(peek()=='\\') {
      ucchar_t uc;
      char_type c = get();
      if(peek() != 'u') { putback(c); break; }
      get();
      uc = parse_ucc_esc();
      if(uc >= 0xd800 && uc <= 0xdbff) { // It's a surrog. pair?
        if(get()!='\\' || get()!='u') {
          throw exception_type("Missing second unicode escape sequence for surrogate pair.");
        }
        ucchar_t uc2 = parse_ucc_esc();
        uc = ((1ul)<<16) + ((uc & (((1ul<<10)-1)<<10)) | (uc2 & ((((1ul)<<10)-1))));
      }
      s += ucc2utf8(uc);
    }
    return s;
  }

  ucchar_t parse_ucc_esc()
  {
    ucchar_t uc = 0;
    char_type c;
    for(int i=0; i<4; ++i) {
      c = ::tolower(get());
      uc <<= 4;
      if     (c>='0' && c<='9') uc|= (c-'0');
      else if(c>='a' && c<='f') uc|= (c-'a'+10);
      else throw exception_type("Invalid hex character while parsing unicode escape.");
    }
    return uc;
  }

  static string_type ucc2utf8(ucchar_t c)
  {
    unsigned char s[5] = {0,0,0,0,0};
    if(c < 0x00000080) {
       s[0] = (c);
    } else if (c < 0x00000800u) {
       s[0] = (0xc0u | (0x1fu & (c >>  6)));
       s[1] = (0x80u | (0x3fu & (c >>  0)));
    } else if (c < 0x00010000u) {
       s[0] = (0xE0u | (0x0fu & (c >> 12)));
       s[1] = (0x80u | (0x3fu & (c >>  6)));
       s[2] = (0x80u | (0x3fu & (c >>  0)));
    } else if (c < 0x00110000u) {
       s[0] = (0xf0u | (0x07u & (c >> 18)));
       s[1] = (0x80u | (0x3fu & (c >> 12)));
       s[2] = (0x80u | (0x3fu & (c >>  6)));
       s[3] = (0x80u | (0x3fu & (c >>  0)));
    }
    return string_type((char*)s);
  }

  //////////////////////////////////////////////////////////////////////////////
  // Compose

protected:

  inline ostream_type & put()
  { if(os_->good()) return *os_; throw exception_type("Compose output stream failed"); }

  /**
   * Compose starting point.
   * @param const var_type&
   * @param ostream_type& os
   */
  void compose_root(const var_type& o)
  {
    try {
      line_ = line_pos_ = 0;
      eof_overread_ = 0;
      is_ = 0;
      if(o.is_unset()) return;
      if((!os_) ||  !os_->good()) throw exception_type("Cannot compose, out stream is 'bad'");
      compose_r(o);
    } catch(const exception_type &e) {
      sstream_type s; s << "JSON composer: " << e.what();
      throw exception_type(s.str());
    }
  }

  /**
   * Recursive composing.
   * @param const var_type&
   * @param ostream_type& os
   */
  void compose_r(const var_type& o)
  {
    if(o.is_unset()) {
      return;
    } else if(o.is_null()) {
      put() << "null";
    } else if(o.is_bool()) {
      put() << (o.b() ? "true" : "false");
    } else if(o.is_int()) {
      put() << o.i();
    } else if(o.is_float()) {
      put() << o.f();
    } else if(o.is_string()) {
      compose_string(o.s());
    } else if(o.is_vector()) {
      put() << "[";
      int end = o.size()-1;
      int i=-1;
      while(++i < end) { compose_r(o.v(i)); put() << ","; }
      if(i<=end) compose_r(o.v(i));
      put() << "]";
    } else if(o.is_map()) {
      put() << "{";
      typename var_type::map_t::const_iterator end = o.m().end();
      for(typename var_type::map_t::const_iterator it=o.m().begin(); it!=end; ++it) {
        compose_object_key(it->first);
        put() << ":";
        compose_r(it->second);
        typename var_type::map_t::const_iterator cit = it;
        if(++cit != end)put() << ",";
      }
      put() << "}";
    }

  }

  /**
   * Normally identically to compose_string. If nonstrict, alphanumeric keys
   * are not escaped using string literals.
   * @param const string_type &s
   */
  void compose_object_key(const string_type &s)
  {
    if(s.empty()) {
      put() << "\"\"";
    } else if(!strict() && std::isalpha(s[0])) {
      typename string_type::const_iterator it=s.begin();
      typename string_type::const_iterator end=s.end();
      while((++it)!=end) {
        if(!std::isalnum(*it) && (*it) != '_') {
          compose_string(s);
          return;
        }
      }
      put() << s;
    } else {
      compose_string(s);
    }
  }

  /**
   * String composition
   * @param const string_type &s
   * @return void
   */
  void compose_string(const string_type &s)
  {
    put() << "\"";
    typename string_type::const_iterator p=s.begin();
    typename string_type::const_iterator e=s.end();
    for(; p!=e; ++p) {
      if((*p) < 0) {
        (*os_) << (*p); // pass through UTF8, no stream bad check here
      } else if((*p) == 0) {
        put() << ucc2uchex(0); // Just to ensure ...
      } else if((*p) != ' ' && (std::iscntrl(*p) || std::isspace(*p))) {
        switch((*p)) {
          case '\n': (*os_) << "\\n"; break;
          case '\r': (*os_) << "\\r"; break;
          case '\t': (*os_) << "\\t"; break;
          case '\f': (*os_) << "\\f"; break;
          case '\v': (*os_) << "\\v"; break;
          case '\a': (*os_) << "\\a"; break;
          case '\b': (*os_) << "\\b"; break;
          default:   (*os_) << ucc2uchex(((1u<<7)-1) & (*p));
        }
      } else if((*p)=='\\' || (*p)=='"') {
        (*os_) << '\\' << (*p);
      } else {
        (*os_) << (*p); // pass through normal char, no stream bad check here
      }
    }
    put() << "\"";
  }

  /**
   * Note: Stripped version, no surrogates
   * @param unsigned uc
   * @return string_type
   */
  inline string_type ucc2uchex(unsigned uc)
  {
    uc &= (1u<<16)-1;
    char s[7] = { '\\','u','0','0','0','0', 0};
    int i = 6;
    while(i<7 && uc!=0) { // uint wrap -> i<0
      char c = (uc & 0x0f);
      uc >>= 4;
      s[--i] = (c<10) ? (c+'0') : (c-10+'a');
    }
    return s;
  }

  //////////////////////////////////////////////////////////////////////////////
  // Instance variables

protected:

  istream_type *is_;
  ostream_type *os_;
  int line_, line_pos_;
  char_type eof_overread_;
  options_type opts_;
};

}}


////////////////////////////////////////////////////////////////////////////////
// Default specialisation

namespace sw {
  typedef detail::basic_json<std::string> json;
}

#endif