Accept large unsigned integers (simdjson#295)

saka1 · lemire · commit c1f27fb848c9 · 2019-09-02T10:50:24.000-04:00
* handle uint64 value in JSON
* Add integer_tests
* Add get_unsigned_integer() on  ParsedJson::BasicIterator
* Write 'u' to tape when the value seems unsigned
* Add to handle 'u' element
* Brush up integer_tests.cpp
* Append tests/integer_tests in .gitignore
* Add comments to is_integer and is_unsigned_integer
diff --git a/.gitignore b/.gitignore
@@ -32,6 +32,7 @@
 /tests/basictests
 /tests/jsoncheck
 /tests/pointercheck
+/tests/integer_tests
 /tools/json2json
 /tools/jsonstats
 /tools/minify
diff --git a/benchmark/parseandstatcompetition.cpp b/benchmark/parseandstatcompetition.cpp
@@ -72,6 +72,10 @@ simdjson_compute_stats(const simdjson::padded_string &p) {
       answer.number_count++;
       tape_idx++; // skipping the integer
       break;
+    case 'u': // we have a long uint
+      answer.number_count++;
+      tape_idx++; // skipping the unsigned integer
+      break;
     case 'd': // we have a double
       answer.number_count++;
       tape_idx++; // skipping the double
diff --git a/benchmark/statisticalmodel.cpp b/benchmark/statisticalmodel.cpp
@@ -78,6 +78,10 @@ stat_t simdjson_compute_stats(const simdjson::padded_string &p) {
       answer.integer_count++;
       tape_idx++; // skipping the integer
       break;
+    case 'u': // we have a long uint
+      answer.integer_count++;
+      tape_idx++; // skipping the integer
+      break;
     case 'd': // we have a double
       answer.float_count++;
       tape_idx++; // skipping the double
diff --git a/include/simdjson/numberparsing.h b/include/simdjson/numberparsing.h
@@ -375,15 +375,20 @@ static never_inline bool parse_large_integer(const uint8_t *const buf,
       found_invalid_number(buf + offset);
 #endif
       return false; // overflow
+    } else if (i == 0x8000000000000000) {
+      constexpr int64_t signed_answer = INT64_MIN;
+      pj.write_tape_s64(signed_answer);
+#ifdef JSON_TEST_NUMBERS // for unit testing
+      found_integer(signed_answer, buf + offset);
+#endif
+      return is_structural_or_whitespace(*p);
     }
   } else {
-    if (i >= 0x8000000000000000) {
-// overflows!
 #ifdef JSON_TEST_NUMBERS // for unit testing
-      found_invalid_number(buf + offset);
+    found_integer(i, buf + offset);
 #endif
-      return false; // overflow
-    }
+    pj.write_tape_u64(i);
+    return is_structural_or_whitespace(*p);
   }
   int64_t signed_answer =
       negative ? -static_cast<int64_t>(i) : static_cast<int64_t>(i);
diff --git a/include/simdjson/parsedjson.h b/include/simdjson/parsedjson.h
@@ -79,6 +79,11 @@ class ParsedJson {
     tape[current_loc++] = *(reinterpret_cast<uint64_t *>(&i));
   }
 
+  really_inline void write_tape_u64(uint64_t i) {
+    write_tape(0, 'u');
+    tape[current_loc++] = i;
+  }
+
   really_inline void write_tape_double(double d) {
     write_tape(0, 'd');
     static_assert(sizeof(d) == sizeof(tape[current_loc]), "mismatch size");
diff --git a/include/simdjson/parsedjsoniterator.h b/include/simdjson/parsedjsoniterator.h
@@ -1,16 +1,15 @@
 #ifndef SIMDJSON_PARSEDJSONITERATOR_H
 #define SIMDJSON_PARSEDJSONITERATOR_H
 
-#include "simdjson/parsedjson.h"
 #include "simdjson/jsonformatutils.h"
+#include "simdjson/parsedjson.h"
 #include <cstring>
 #include <iostream>
-#include <limits>
 #include <iterator>
+#include <limits>
 
 namespace simdjson {
-template <size_t max_depth>
-class ParsedJson::BasicIterator {
+template <size_t max_depth> class ParsedJson::BasicIterator {
   // might throw InvalidJSON if ParsedJson is invalid
 public:
   explicit BasicIterator(ParsedJson &pj_);
@@ -51,6 +50,14 @@ class ParsedJson::BasicIterator {
     return static_cast<int64_t>(pj->tape[location + 1]);
   }
 
+  // get the value as uint64
+  inline uint64_t get_unsigned_integer() const {
+    if (location + 1 >= tape_length) {
+      return 0; // default value in case of error
+    }
+    return pj->tape[location + 1];
+  }
+
   // get the string value at this node (NULL ended); valid only if we're at "
   // note that tabs, and line endings are escaped in the returned value (see
   // print_with_escapes) return value is valid UTF-8 It may contain NULL chars
@@ -90,10 +97,26 @@ class ParsedJson::BasicIterator {
 
   inline bool is_string() const { return get_type() == '"'; }
 
+  // Returns true if the current type of node is an signed integer.
+  // You can get its value with `get_integer()`.
   inline bool is_integer() const { return get_type() == 'l'; }
 
+  // Returns true if the current type of node is an unsigned integer.
+  // You can get its value with `get_unsigned_integer()`.
+  //
+  // NOTE:
+  // Only a large value, which is out of range of a 64-bit signed integer, is
+  // represented internally as an unsigned node. On the other hand, a typical
+  // positive integer, such as 1, 42, or 1000000, is as a signed node.
+  // Be aware this function returns false for a signed node.
+  inline bool is_unsigned_integer() const { return get_type() == 'u'; }
+
   inline bool is_double() const { return get_type() == 'd'; }
 
+  inline bool is_number() const {
+    return is_integer() || is_unsigned_integer() || is_double();
+  }
+
   inline bool is_true() const { return get_type() == 't'; }
 
   inline bool is_false() const { return get_type() == 'f'; }
@@ -110,7 +133,7 @@ class ParsedJson::BasicIterator {
   // (in case of repeated keys, this only finds the first one).
   // We seek the key using C's strcmp so if your JSON strings contain
   // NULL chars, this would trigger a false positive: if you expect that
-  // to be the case, take extra precautions. 
+  // to be the case, take extra precautions.
   // Furthermore, we do the comparison character-by-character
   // without taking into account Unicode equivalence.
   inline bool move_to_key(const char *key);
@@ -230,21 +253,28 @@ class ParsedJson::BasicIterator {
 };
 
 template <size_t max_depth>
-WARN_UNUSED
-bool ParsedJson::BasicIterator<max_depth>::is_ok() const { return location < tape_length; }
+WARN_UNUSED bool ParsedJson::BasicIterator<max_depth>::is_ok() const {
+  return location < tape_length;
+}
 
 // useful for debuging purposes
 template <size_t max_depth>
-size_t ParsedJson::BasicIterator<max_depth>::get_tape_location() const { return location; }
+size_t ParsedJson::BasicIterator<max_depth>::get_tape_location() const {
+  return location;
+}
 
 // useful for debuging purposes
 template <size_t max_depth>
-size_t ParsedJson::BasicIterator<max_depth>::get_tape_length() const { return tape_length; }
+size_t ParsedJson::BasicIterator<max_depth>::get_tape_length() const {
+  return tape_length;
+}
 
 // returns the current depth (start at 1 with 0 reserved for the fictitious root
 // node)
 template <size_t max_depth>
-size_t ParsedJson::BasicIterator<max_depth>::get_depth() const { return depth; }
+size_t ParsedJson::BasicIterator<max_depth>::get_depth() const {
+  return depth;
+}
 
 // A scope is a series of nodes at the same depth, typically it is either an
 // object ({) or an array ([). The root node has type 'r'.
@@ -268,8 +298,8 @@ bool ParsedJson::BasicIterator<max_depth>::move_forward() {
   } else if ((current_type == ']') || (current_type == '}')) {
     // Leaving a scope.
     depth--;
-  } else if ((current_type == 'd') || (current_type == 'l')) {
-    // d and l types use 2 locations on the tape, not just one.
+  } else if (is_number()) {
+    // these types use 2 locations on the tape, not just one.
     location += 1;
   }
 
@@ -305,7 +335,8 @@ bool ParsedJson::BasicIterator<max_depth>::move_to_key(const char *key) {
 }
 
 template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::move_to_key(const char *key, uint32_t length) {
+bool ParsedJson::BasicIterator<max_depth>::move_to_key(const char *key,
+                                                       uint32_t length) {
   if (down()) {
     do {
       assert(is_string());
@@ -339,33 +370,31 @@ bool ParsedJson::BasicIterator<max_depth>::move_to_index(uint32_t index) {
   return false;
 }
 
-template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::prev() {
+template <size_t max_depth> bool ParsedJson::BasicIterator<max_depth>::prev() {
   size_t target_location = location;
   to_start_scope();
   size_t npos = location;
-  if(target_location == npos) {
+  if (target_location == npos) {
     return false; // we were already at the start
   }
   size_t oldnpos;
   // we have that npos < target_location here
   do {
     oldnpos = npos;
     if ((current_type == '[') || (current_type == '{')) {
-    // we need to jump
+      // we need to jump
       npos = (current_val & JSON_VALUE_MASK);
     } else {
       npos = npos + ((current_type == 'd' || current_type == 'l') ? 2 : 1);
     }
-  } while(npos < target_location);
+  } while (npos < target_location);
   location = oldnpos;
   current_val = pj->tape[location];
   current_type = current_val >> 56;
   return true;
 }
 
-template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::up() {
+template <size_t max_depth> bool ParsedJson::BasicIterator<max_depth>::up() {
   if (depth == 1) {
     return false; // don't allow moving back to root
   }
@@ -378,8 +407,7 @@ bool ParsedJson::BasicIterator<max_depth>::up() {
   return true;
 }
 
-template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::down() {
+template <size_t max_depth> bool ParsedJson::BasicIterator<max_depth>::down() {
   if (location + 1 >= tape_length) {
     return false;
   }
@@ -407,14 +435,13 @@ void ParsedJson::BasicIterator<max_depth>::to_start_scope() {
   current_type = (current_val >> 56);
 }
 
-template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::next() {
+template <size_t max_depth> bool ParsedJson::BasicIterator<max_depth>::next() {
   size_t npos;
   if ((current_type == '[') || (current_type == '{')) {
     // we need to jump
     npos = (current_val & JSON_VALUE_MASK);
   } else {
-    npos = location + ((current_type == 'd' || current_type == 'l') ? 2 : 1);
+    npos = location + (is_number() ? 2 : 1);
   }
   uint64_t next_val = pj->tape[npos];
   uint8_t next_type = (next_val >> 56);
@@ -456,14 +483,17 @@ ParsedJson::BasicIterator<max_depth>::BasicIterator(ParsedJson &pj_)
 }
 
 template <size_t max_depth>
-ParsedJson::BasicIterator<max_depth>::BasicIterator(const BasicIterator &o) noexcept
-    : pj(o.pj), depth(o.depth), location(o.location), tape_length(o.tape_length),
-      current_type(o.current_type), current_val(o.current_val) {
+ParsedJson::BasicIterator<max_depth>::BasicIterator(
+    const BasicIterator &o) noexcept
+    : pj(o.pj), depth(o.depth), location(o.location),
+      tape_length(o.tape_length), current_type(o.current_type),
+      current_val(o.current_val) {
   memcpy(depth_index, o.depth_index, (depth + 1) * sizeof(depth_index[0]));
 }
 
 template <size_t max_depth>
-ParsedJson::BasicIterator<max_depth> &ParsedJson::BasicIterator<max_depth>::operator =(const BasicIterator &o) noexcept {
+ParsedJson::BasicIterator<max_depth> &ParsedJson::BasicIterator<max_depth>::
+operator=(const BasicIterator &o) noexcept {
   pj = o.pj;
   depth = o.depth;
   location = o.location;
@@ -475,7 +505,8 @@ ParsedJson::BasicIterator<max_depth> &ParsedJson::BasicIterator<max_depth>::oper
 }
 
 template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::print(std::ostream &os, bool escape_strings) const {
+bool ParsedJson::BasicIterator<max_depth>::print(std::ostream &os,
+                                                 bool escape_strings) const {
   if (!is_ok()) {
     return false;
   }
@@ -495,6 +526,9 @@ bool ParsedJson::BasicIterator<max_depth>::print(std::ostream &os, bool escape_s
   case 'l': // we have a long int
     os << get_integer();
     break;
+  case 'u':
+    os << get_unsigned_integer();
+    break;
   case 'd':
     os << get_double();
     break;
@@ -520,7 +554,8 @@ bool ParsedJson::BasicIterator<max_depth>::print(std::ostream &os, bool escape_s
 }
 
 template <size_t max_depth>
-bool ParsedJson::BasicIterator<max_depth>::move_to(const char *pointer, uint32_t length) {
+bool ParsedJson::BasicIterator<max_depth>::move_to(const char *pointer,
+                                                   uint32_t length) {
   char *new_pointer = nullptr;
   if (pointer[0] == '#') {
     // Converting fragment representation to string representation
diff --git a/jsonchecker/pass21.json b/jsonchecker/pass21.json
diff --git a/src/parsedjson.cpp b/src/parsedjson.cpp
@@ -176,6 +176,14 @@ bool ParsedJson::print_json(std::ostream &os) {
       }
       os << static_cast<int64_t>(tape[++tape_idx]);
       break;
+    case 'u':
+      if (tape_idx + 1 >= how_many) {
+        delete[] in_object;
+        delete[] in_object_idx;
+        return false;
+      }
+      os << tape[++tape_idx];
+      break;
     case 'd': // we have a double
       if (tape_idx + 1 >= how_many) {
         delete[] in_object;
@@ -273,6 +281,12 @@ bool ParsedJson::dump_raw_tape(std::ostream &os) {
       }
       os << "integer " << static_cast<int64_t>(tape[++tape_idx]) << "\n";
       break;
+    case 'u': // we have a long uint
+      if (tape_idx + 1 >= how_many) {
+        return false;
+      }
+      os << "unsigned integer " << tape[++tape_idx] << "\n";
+      break;
     case 'd': // we have a double
       os << "float ";
       if (tape_idx + 1 >= how_many) {
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
@@ -7,6 +7,7 @@ endif()
 add_cpp_test(basictests)
 add_cpp_test(jsoncheck)
 add_cpp_test(pointercheck)
+add_cpp_test(integer_tests)
 
 ## This causes problems
 # add_executable(singleheader ./singleheadertest.cpp ${PROJECT_SOURCE_DIR}/singleheader/simdjson.cpp)
diff --git a/tests/integer_tests.cpp b/tests/integer_tests.cpp
diff --git a/tests/numberparsingcheck.cpp b/tests/numberparsingcheck.cpp
diff --git a/tools/jsonstats.cpp b/tools/jsonstats.cpp
