This is a bug fix: our prev function was buggy. (simdjson#291)

lemire · web-flow · commit f667d4965d0f · 2019-08-23T18:59:43.000-04:00
diff --git a/include/simdjson/parsedjsoniterator.h b/include/simdjson/parsedjsoniterator.h
@@ -185,6 +185,9 @@ class ParsedJson::BasicIterator {
   // Thus, given [true, null, {"a":1}, [1,2]], we would visit ], }, null, true
   // when starting at the end of the scope. At the object ({) or at the array
   // ([), you can issue a "down" to visit their content.
+  // Performance warning: This function is implemented by starting again
+  // from the beginning of the scope and scanning forward. You should expect
+  // it to be relatively slow.
   inline bool prev();
 
   // Moves back to either the containing array or object (type { or [) from
@@ -338,22 +341,26 @@ bool ParsedJson::BasicIterator<max_depth>::move_to_index(uint32_t index) {
 
 template <size_t max_depth>
 bool ParsedJson::BasicIterator<max_depth>::prev() {
-  if (location - 1 < depth_index[depth].start_of_scope) {
-    return false;
+  size_t target_location = location;
+  to_start_scope();
+  size_t npos = location;
+  if(target_location == npos) {
+    return false; // we were already at the start
   }
-  location -= 1;
-  current_val = pj->tape[location];
-  current_type = (current_val >> 56);
-  if ((current_type == ']') || (current_type == '}')) {
+  size_t oldnpos;
+  // we have that npos < target_location here
+  do {
+    oldnpos = npos;
+    if ((current_type == '[') || (current_type == '{')) {
     // we need to jump
-    size_t new_location = (current_val & JSON_VALUE_MASK);
-    if (new_location < depth_index[depth].start_of_scope) {
-      return false; // shoud never happen
+      npos = (current_val & JSON_VALUE_MASK);
+    } else {
+      npos = npos + ((current_type == 'd' || current_type == 'l') ? 2 : 1);
     }
-    location = new_location;
-    current_val = pj->tape[location];
-    current_type = (current_val >> 56);
-  }
+  } while(npos < target_location);
+  location = oldnpos;
+  current_val = pj->tape[location];
+  current_type = current_val >> 56;
   return true;
 }
 
diff --git a/tests/basictests.cpp b/tests/basictests.cpp
@@ -9,6 +9,74 @@
 
 #include "simdjson/jsonparser.h"
 
+
+// returns true if successful
+bool navigate_test() {
+  std::string json = "{"
+        "\"Image\": {"
+            "\"Width\":  800,"
+            "\"Height\": 600,"
+            "\"Title\":  \"View from 15th Floor\","
+            "\"Thumbnail\": {"
+            "    \"Url\":    \"http://www.example.com/image/481989943\","
+            "    \"Height\": 125,"
+            "    \"Width\":  100"
+            "},"
+            "\"Animated\" : false,"
+            "\"IDs\": [116, 943, 234, 38793]"
+          "}"
+      "}";
+
+  simdjson::ParsedJson pj = simdjson::build_parsed_json(json);
+  if (!pj.is_valid()) {
+      printf("Something is wrong in navigate: %s.\n", json.c_str());
+      return false;
+  }
+  simdjson::ParsedJson::Iterator pjh(pj);
+  if(!pjh.is_object()) {
+    printf("Root should be object\n");
+    return false;
+  }
+  if(!pjh.down()) {
+    printf("Root should not be emtpy\n");
+    return false;
+  }
+  if(!pjh.is_string()) {
+    printf("Object should start with string key\n");
+    return false;
+  }
+  if(pjh.prev()) {
+    printf("We should not be able to go back from the start of the scope.\n");
+    return false;
+  }
+  if(strcmp(pjh.get_string(),"Image")!=0) {
+    printf("There should be a single key, image.\n");
+    return false;
+  }
+  pjh.move_to_value();
+  if(!pjh.is_object()) {
+    printf("Value of image should be object\n");
+    return false;
+  }
+  if(!pjh.down()) {
+    printf("Image key should not be emtpy\n");
+    return false;
+  }
+  if(!pjh.next()) {
+    printf("key should have a value\n");
+    return false;
+  }
+  if(!pjh.prev()) {
+    printf("We should go back to the key.\n");
+    return false;
+  }
+  if(strcmp(pjh.get_string(),"Width")!=0) {
+    printf("There should be a  key Width.\n");
+    return false;
+  }
+  return true;
+}
+
 // returns true if successful
 bool skyprophet_test() {
   const size_t n_records = 100000;
@@ -68,6 +136,8 @@ bool skyprophet_test() {
 
 int main() {
   std::cout << "Running basic tests." << std::endl;
+  if (!navigate_test())
+    return EXIT_FAILURE;
   if (!skyprophet_test())
     return EXIT_FAILURE;
   std::cout << "Basic tests are ok." << std::endl;
