O(n^2) complexity in json_next_elem

[numo68]

I am trying to iterate through an array using json_next_elem(). The function returns a handle suitable to be passed to the next invocation, which is a common idiom and the user's expectation is definitely that this handle remembers, where to continue with the next search, and such iteration is thus O(n).

If I try the following code

  const char* json = "[1,2,3,4,5]";
  void* handle = NULL;
  int idx;
  struct json_token val;
  while ((handle = json_next_elem(json, strlen(json), handle, "", &idx, &val))) {
    fprintf(stderr, "idx %d\n", idx);
  }

and place a breakpoint at json_parse_value(), the method is in fact called 36 times, with the case '[' being hit 6 times, meaning that the handle in fact only records, what index I want to reach, and searches for it through the whole array, using a simple pointer compare to know where to stop. That makes the function O(n^2) and unusable for anything more than a few elements. In fact we've found the problem trying to parse a file using a simple schema with less than ten thousand elements. which resulted in calling some frozen's functions 73 million times.

I know that I can use json_walk, that is however working around an issue and gets ugly pretty quick.

If this is how the code was intended to work, or there is a way to iterate in a truly linear way, please document it to avoid surprises. If it is not, a fix would be appreciated.

Thanks

[ShivaPriyanShanmuga]

I'd like to try and work on this issue, I'm new to the Repo so give me like a couple of days and I'll get back to you! : )

[numo68]

Hello @ShivaPriyanShanmuga , thanks for looking into this. From a cursory look, the handle could be a pointer to the next element to be parsed and struct next_data could track the recursion depth instead of doing string manipulation to keep things efficient. I.e. something like

• advise the user in the documentation that an empty path is preferred
• with a NULL handle, walk until the path's array or object start (if path non-empty), walk and return the first item, return the next pointer as the handle
• with a non-NULL handle, fake a top-level next_data walked past the object/array start, walk and return the item pointed to, return the next pointer as the handle
• if the object/array end is encountered at the recursion level we started, we are done

To be honest I'd even suggest to drop path from the json_next_key / json_next_elem API, one can always search for it explicitly if needed, but I guess a breaking change is not possible here. And due to the recursive way of json_parse_* there will be probably a need to devise a way to stop the json_walk early.

Good unit-test coverage is of course necessary.

Thanks