Stack overflow for circular reference

[tregua87]

I noticed that cJSON does not correctly handle objects with circular references (commit 3249730). For instance, I can have 3 objects that points each other, e.g., A->B->C->A, the function cJSON_Duplicate enters in a infinite recursions. Here is a simple example:

#include <cjson/cJSON.h>

#include <stdlib.h>
#include <stdint.h>

int main(int argc, char** argv) {

        cJSON *o = cJSON_CreateArray();
        cJSON *a = cJSON_CreateArray();
        cJSON *b = cJSON_CreateArray();

        cJSON_AddItemToArray(o, a);
        cJSON_AddItemToArray(a, b);
        cJSON_AddItemToArray(b, o);

        cJSON *x = cJSON_Duplicate(o, 1);

        cJSON_Delete(o);
        cJSON_Delete(a);
        cJSON_Delete(b);
        cJSON_Delete(x);

        return 0;
}

The problem seems that cJSON_Duplicate has no way to know if the child has been already processed, line 2773 in my version:

/* Walk the ->next chain for the child. */
    child = item->child;
    while (child != NULL)
    {
        newchild = cJSON_Duplicate(child, true); /* Duplicate (with recurse) each item in the ->next chain *./
        if (!newchild)
        {
            goto fail;
        }

I would propose a fix but I am not sure how to operate. I see two possible solutions:

• avoiding circular references when AddItem is used
• stop infinite recursion in cJSON_Duplicate or similar.

Can you hint me if you were already aware of this problem, and if you plan to fix it?

[PeterAlfredLee]

Thanks for your report. As I said in #882, cjson is designed to believe the input arguments are correct. It leave the validation of input arguments to the caller, which makes cjson has a relative good performance.

Can you hint me if you were already aware of this problem, and if you plan to fix it?

Yes, we are aware of circular references. We can handle this by iterating all items and check if there are circular references, but this is no doubt a time consuming operation. I do not like this.

Feel free to tell me if you have better ideas.

[tregua87]

I suggest implementing a set with a tree-based structure, something like this (http://web.cs.wpi.edu/~cs2102/common/kathi-notes/set-impl-w-trees.html). With this implementation, you need a log(N) time to determine if a node has been already processed.

You prepare a set of visited nodes. Then, while walking through the duplication, you abort if a node is already traversed. You can easily model the JSON objects via their virtual address, which fit into a binary tree.

You do not need the tree to stay balanced IMO. In that case, we can use a black-red tree.

I see the problem of adding such a big structure tho. It is not even C++ where you can leverage std::set structures.