iOS/Pods/Realm/include/core/realm/util/json_parser.hpp

   1 /*************************************************************************
   2  *
   3  * REALM CONFIDENTIAL
   4  * __________________
   5  *
   6  *  [2011] - [2016] Realm Inc
   7  *  All Rights Reserved.
   8  *
   9  * NOTICE:  All information contained herein is, and remains
  10  * the property of Realm Incorporated and its suppliers,
  11  * if any.  The intellectual and technical concepts contained
  12  * herein are proprietary to Realm Incorporated
  13  * and its suppliers and may be covered by U.S. and Foreign Patents,
  14  * patents in process, and are protected by trade secret or copyright law.
  15  * Dissemination of this information or reproduction of this material
  16  * is strictly forbidden unless prior written permission is obtained
  17  * from Realm Incorporated.
  18  *
  19  **************************************************************************/
  20
  21 #ifndef REALM_UTIL_JSON_PARSER_HPP
  22 #define REALM_UTIL_JSON_PARSER_HPP
  23
  24 #include <system_error>
  25 #include <algorithm>
  26 #include <cstdlib>
  27 #include <cctype>
  28
  29 #include <realm/string_data.hpp>
  30
  31 namespace realm {
  32 namespace util {
  33
  34 /// A JSON parser that neither allocates heap memory nor throws exceptions.
  35 ///
  36 /// The parser takes as input a range of characters, and emits a stream of events
  37 /// representing the structure of the JSON document.
  38 ///
  39 /// Parser errors are represented as `std::error_condition`s.
  40 class JSONParser {
  41 public:
  42     using InputIterator = const char*;
  43
  44     enum class EventType {
  45         number,
  46         string,
  47         boolean,
  48         null,
  49         array_begin,
  50         array_end,
  51         object_begin,
  52         object_end
  53     };
  54
  55     using Range = StringData;
  56
  57     struct Event {
  58         EventType type;
  59         Range range;
  60         Event(EventType type): type(type) {}
  61
  62         union {
  63             bool boolean;
  64             double number;
  65         };
  66
  67         StringData escaped_string_value() const noexcept;
  68
  69         /// Unescape the string value into \a buffer.
  70         /// The type of this event must be EventType::string.
  71         ///
  72         /// \param buffer is a pointer to a buffer big enough to hold the
  73         /// unescaped string value. The unescaped string is guaranteed to be
  74         /// shorter than the escaped string, so escaped_string_value().size() can
  75         /// be used as an upper bound. Unicode sequences of the form "\uXXXX"
  76         /// will be converted to UTF-8 sequences. Note that the escaped form of
  77         /// a unicode point takes exactly 6 bytes, which is also the maximum
  78         /// possible length of a UTF-8 encoded codepoint.
  79         StringData unescape_string(char* buffer) const noexcept;
  80     };
  81
  82     enum class Error {
  83         unexpected_token = 1,
  84         unexpected_end_of_stream = 2
  85     };
  86
  87     JSONParser(StringData);
  88
  89     /// Parse the input data, and call f repeatedly with an argument of type Event
  90     /// representing the token that the parser encountered.
  91     ///
  92     /// The stream of events is "flat", which is to say that it is the responsibility
  93     /// of the function f to keep track of any nested object structures as it deems
  94     /// appropriate.
  95     ///
  96     /// This function is guaranteed to never throw, as long as f never throws.
  97     template<class F>
  98     std::error_condition parse(F&& f) noexcept(noexcept(f(std::declval<Event>())));
  99
 100     class ErrorCategory: public std::error_category {
 101     public:
 102         const char* name() const noexcept final;
 103         std::string message(int) const final;
 104     };
 105     static const ErrorCategory error_category;
 106 private:
 107     enum Token: char {
 108         object_begin = '{',
 109         object_end   = '}',
 110         array_begin  = '[',
 111         array_end    = ']',
 112         colon        = ':',
 113         comma        = ',',
 114         dquote       = '"',
 115         escape       = '\\',
 116         minus        = '-',
 117         space        = ' ',
 118         tab          = '\t',
 119         cr           = '\r',
 120         lf           = '\n',
 121     };
 122
 123     InputIterator m_current;
 124     InputIterator m_end;
 125
 126     template<class F>
 127     std::error_condition parse_object(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 128     template<class F>
 129     std::error_condition parse_pair(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 130     template<class F>
 131     std::error_condition parse_array(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 132     template<class F>
 133     std::error_condition parse_number(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 134     template<class F>
 135     std::error_condition parse_string(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 136     template<class F>
 137     std::error_condition parse_value(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 138     template<class F>
 139     std::error_condition parse_boolean(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 140     template<class F>
 141     std::error_condition parse_null(F&& f) noexcept(noexcept(f(std::declval<Event>())));
 142
 143     std::error_condition expect_token(char, Range& out_range) noexcept;
 144     std::error_condition expect_token(Token, Range& out_range) noexcept;
 145
 146     // Returns true unless EOF was reached.
 147     bool peek_char(char& out_c) noexcept;
 148     bool peek_token(Token& out_t) noexcept;
 149     bool is_whitespace(Token t) noexcept;
 150     void skip_whitespace() noexcept;
 151 };
 152
 153 std::error_condition make_error_condition(JSONParser::Error e);
 154
 155 } // namespace util
 156 } // namespace realm
 157
 158 namespace std {
 159 template<>
 160 struct is_error_condition_enum<realm::util::JSONParser::Error> {
 161     static const bool value = true;
 162 };
 163 }
 164
 165 namespace realm {
 166 namespace util {
 167
 168 /// Implementation:
 169
 170
 171 inline JSONParser::JSONParser(StringData input):
 172     m_current(input.data()), m_end(input.data() + input.size())
 173 {
 174 }
 175
 176 template<class F>
 177 std::error_condition JSONParser::parse(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 178 {
 179     return parse_value(f);
 180 }
 181
 182 template<class F>
 183 std::error_condition JSONParser::parse_object(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 184 {
 185     Event event{EventType::object_begin};
 186     auto ec = expect_token(Token::object_begin, event.range);
 187     if (ec)
 188         return ec;
 189     ec = f(event);
 190     if (ec)
 191         return ec;
 192
 193     while (true) {
 194         ec = expect_token(Token::object_end, event.range);
 195         if (!ec) {
 196             // End of object
 197             event.type = EventType::object_end;
 198             ec = f(event);
 199             if (ec)
 200                 return ec;
 201             break;
 202         }
 203
 204         if (ec != Error::unexpected_token)
 205             return ec;
 206
 207         ec = parse_pair(f);
 208         if (ec)
 209             return ec;
 210
 211         skip_whitespace();
 212
 213         Token t;
 214         if (peek_token(t)) {
 215             if (t == Token::object_end) {
 216                 // Fine, will terminate on next iteration
 217             }
 218             else if (t == Token::comma)
 219                 ++m_current; // OK, because peek_char returned true
 220             else
 221                 return Error::unexpected_token;
 222         }
 223         else {
 224             return Error::unexpected_end_of_stream;
 225         }
 226     }
 227
 228     return std::error_condition{};
 229 }
 230
 231 template<class F>
 232 std::error_condition JSONParser::parse_pair(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 233 {
 234     skip_whitespace();
 235
 236     auto ec = parse_string(f);
 237     if (ec)
 238         return ec;
 239
 240     skip_whitespace();
 241
 242     Token t;
 243     if (peek_token(t)) {
 244         if (t == Token::colon) {
 245             ++m_current;
 246         }
 247         else {
 248             return Error::unexpected_token;
 249         }
 250     }
 251
 252     return parse_value(f);
 253 }
 254
 255 template<class F>
 256 std::error_condition JSONParser::parse_array(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 257 {
 258     Event event{EventType::array_begin};
 259     auto ec = expect_token(Token::array_begin, event.range);
 260     if (ec)
 261         return ec;
 262     ec = f(event);
 263     if (ec)
 264         return ec;
 265
 266     while (true) {
 267         ec = expect_token(Token::array_end, event.range);
 268         if (!ec) {
 269             // End of array
 270             event.type = EventType::array_end;
 271             ec = f(event);
 272             if (ec)
 273                 return ec;
 274             break;
 275         }
 276
 277         if (ec != Error::unexpected_token)
 278             return ec;
 279
 280         ec = parse_value(f);
 281         if (ec)
 282             return ec;
 283
 284         skip_whitespace();
 285
 286         Token t;
 287         if (peek_token(t)) {
 288             if (t == Token::array_end) {
 289                 // Fine, will terminate next iteration.
 290             }
 291             else if (t == Token::comma)
 292                 ++m_current; // OK, because peek_char returned true
 293             else
 294                 return Error::unexpected_token;
 295         }
 296         else {
 297             return Error::unexpected_end_of_stream;
 298         }
 299     }
 300
 301     return std::error_condition{};
 302 }
 303
 304 template<class F>
 305 std::error_condition JSONParser::parse_number(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 306 {
 307     static const size_t buffer_size = 64;
 308     char buffer[buffer_size] = {0};
 309     size_t bytes_to_copy = std::min<size_t>(m_end - m_current, buffer_size - 1);
 310     if (bytes_to_copy == 0)
 311         return Error::unexpected_end_of_stream;
 312
 313     if (std::isspace(*m_current)) {
 314         // JSON has a different idea of what constitutes whitespace than isspace(),
 315         // but strtod() uses isspace() to skip initial whitespace. We have already
 316         // skipped whitespace that JSON considers valid, so if there is any whitespace
 317         // at m_current now, it is invalid according to JSON, and so is an error.
 318         return Error::unexpected_token;
 319     }
 320
 321     switch (m_current[0]) {
 322         case 'N':
 323             // strtod() parses "NAN", JSON does not.
 324         case 'I':
 325             // strtod() parses "INF", JSON does not.
 326         case 'p':
 327         case 'P':
 328             // strtod() may parse exponent notation, JSON does not.
 329             return Error::unexpected_token;
 330         case '0':
 331             if (bytes_to_copy > 2 && (m_current[1] == 'x' || m_current[1] == 'X')) {
 332                 // strtod() parses hexadecimal, JSON does not.
 333                 return Error::unexpected_token;
 334             }
 335     }
 336
 337     std::copy(m_current, m_current + bytes_to_copy, buffer);
 338
 339     char* endp = nullptr;
 340     Event event{EventType::number};
 341     event.number = std::strtod(buffer, &endp);
 342
 343     if (endp == buffer) {
 344         return Error::unexpected_token;
 345     }
 346     size_t num_bytes_consumed = endp - buffer;
 347     m_current += num_bytes_consumed;
 348     return f(event);
 349 }
 350
 351 template<class F>
 352 std::error_condition JSONParser::parse_string(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 353 {
 354     InputIterator p = m_current;
 355     if (p >= m_end)
 356         return Error::unexpected_end_of_stream;
 357
 358     auto count_num_escapes_backwards = [](const char* p, const char* begin) -> size_t {
 359         size_t result = 0;
 360         for (; p > begin && *p == Token::escape; ++p)
 361             ++result;
 362         return result;
 363     };
 364
 365     Token t = static_cast<Token>(*p);
 366     InputIterator inner_end;
 367     if (t == Token::dquote) {
 368         inner_end = m_current;
 369         do {
 370             inner_end = std::find(inner_end + 1, m_end, Token::dquote);
 371             if (inner_end == m_end)
 372                 return Error::unexpected_end_of_stream;
 373         } while (count_num_escapes_backwards(inner_end - 1, m_current) % 2 == 1);
 374
 375         Event event{EventType::string};
 376         event.range = Range(m_current, inner_end - m_current + 1);
 377         m_current = inner_end + 1;
 378         return f(event);
 379     }
 380     return Error::unexpected_token;
 381 }
 382
 383 template<class F>
 384 std::error_condition JSONParser::parse_boolean(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 385 {
 386     auto first_nonalpha = std::find_if_not(m_current, m_end, [](auto c) { return std::isalpha(c); });
 387
 388     Event event{EventType::boolean};
 389     event.range = Range(m_current, first_nonalpha - m_current);
 390     if (event.range == "true") {
 391         event.boolean = true;
 392         m_current += 4;
 393         return f(event);
 394     }
 395     else if (event.range == "false") {
 396         event.boolean = false;
 397         m_current += 5;
 398         return f(event);
 399     }
 400
 401     return Error::unexpected_token;
 402 }
 403
 404 template<class F>
 405 std::error_condition JSONParser::parse_null(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 406 {
 407     auto first_nonalpha = std::find_if_not(m_current, m_end, [](auto c) { return std::isalpha(c); });
 408
 409     Event event{EventType::null};
 410     event.range = Range(m_current, first_nonalpha - m_current);
 411     if (event.range == "null") {
 412         m_current += 4;
 413         return f(event);
 414     }
 415
 416     return Error::unexpected_token;
 417 }
 418
 419 template<class F>
 420 std::error_condition JSONParser::parse_value(F&& f) noexcept(noexcept(f(std::declval<Event>())))
 421 {
 422     skip_whitespace();
 423
 424     if (m_current >= m_end)
 425         return Error::unexpected_end_of_stream;
 426
 427     if (*m_current == Token::object_begin)
 428         return parse_object(f);
 429
 430     if (*m_current == Token::array_begin)
 431         return parse_array(f);
 432
 433     if (*m_current == 't' || *m_current == 'f')
 434         return parse_boolean(f);
 435
 436     if (*m_current == 'n')
 437         return parse_null(f);
 438
 439     if (*m_current == Token::dquote)
 440         return parse_string(f);
 441
 442     return parse_number(f);
 443 }
 444
 445 inline
 446 bool JSONParser::is_whitespace(Token t) noexcept
 447 {
 448     switch (t) {
 449         case Token::space:
 450         case Token::tab:
 451         case Token::cr:
 452         case Token::lf:
 453             return true;
 454         default:
 455             return false;
 456     }
 457 }
 458
 459 inline
 460 void JSONParser::skip_whitespace() noexcept
 461 {
 462     while (m_current < m_end && is_whitespace(static_cast<Token>(*m_current)))
 463         ++m_current;
 464 }
 465
 466 inline
 467 std::error_condition JSONParser::expect_token(char c, Range& out_range) noexcept
 468 {
 469     skip_whitespace();
 470     if (m_current == m_end)
 471         return Error::unexpected_end_of_stream;
 472     if (*m_current == c) {
 473         out_range = Range(m_current, 1);
 474         ++m_current;
 475         return std::error_condition{};
 476     }
 477     return Error::unexpected_token;
 478 }
 479
 480 inline
 481 std::error_condition JSONParser::expect_token(Token t, Range& out_range) noexcept
 482 {
 483     return expect_token(static_cast<char>(t), out_range);
 484 }
 485
 486 inline
 487 bool JSONParser::peek_char(char& out_c) noexcept
 488 {
 489     if (m_current < m_end) {
 490         out_c = *m_current;
 491         return true;
 492     }
 493     return false;
 494 }
 495
 496 inline
 497 bool JSONParser::peek_token(Token& out_t) noexcept
 498 {
 499     if (m_current < m_end) {
 500         out_t = static_cast<Token>(*m_current);
 501         return true;
 502     }
 503     return false;
 504 }
 505
 506 inline
 507 StringData JSONParser::Event::escaped_string_value() const noexcept
 508 {
 509     REALM_ASSERT(type == EventType::string);
 510     REALM_ASSERT(range.size() >= 2);
 511     return StringData(range.data() + 1, range.size() - 2);
 512 }
 513
 514 template<class OS>
 515 OS& operator<<(OS& os, JSONParser::EventType type)
 516 {
 517     switch (type) {
 518         case JSONParser::EventType::number:       os << "number"; return os;
 519         case JSONParser::EventType::string:       os << "string"; return os;
 520         case JSONParser::EventType::boolean:      os << "boolean"; return os;
 521         case JSONParser::EventType::null:         os << "null"; return os;
 522         case JSONParser::EventType::array_begin:  os << "["; return os;
 523         case JSONParser::EventType::array_end:    os << "]"; return os;
 524         case JSONParser::EventType::object_begin: os << "{"; return os;
 525         case JSONParser::EventType::object_end:   os << "}"; return os;
 526     }
 527     REALM_UNREACHABLE();
 528 }
 529
 530 template<class OS>
 531 OS& operator<<(OS& os, const JSONParser::Event& e) {
 532     os << e.type;
 533     switch (e.type) {
 534         case JSONParser::EventType::number:       return os << "(" << e.number << ")";
 535         case JSONParser::EventType::string:       return os << "(" << e.range << ")";
 536         case JSONParser::EventType::boolean:      return os << "(" << e.boolean << ")";
 537         default: return os;
 538     }
 539 }
 540
 541 } // namespace util
 542 } // namespace realm
 543
 544 #endif // REALM_UTIL_JSON_PARSER_HPP
 545