Fast & Reliable Cloud Backups

For MySQL, MongoDB, Linux, Unix

Get Started

Jul 14, 2016

Bidirectional Relationship Support in JSON

Posted by Dennis

feature photo

This is a guest post from Nermin Hajdarbegovic of the Toptal blog. To see the original click here: https://www.toptal.com/freelance/productivity-travel-hardware

Ever tried to create a JSON data structure that includes entities that have a bidirectional relationship (i.e., circular reference)? If you have, you’ve likely seen a JavaScript error along the lines of “Uncaught TypeError: Converting circular structure to JSON”. Or if you’re a Java developer who uses Jackson library, you may have encountered “Could not write JSON: Infinite recursion (StackOverflowError) with root cause java.lang.StackOverflowError”.

JSON Bidirectional Relationship Challenge

This article provides a robust working approach to creating JSON structures that include a bidirectional relationship without resulting in these errors.

Often, the solutions that are presented to this problem entail workarounds that basically side-step, but don’t really address, the issue. Examples include using Jackson annotation types like @JsonManagedReference and @JsonBackReference (which simply omits the back reference from serialization) or using @JsonIgnore to simply ignore one of the sides of the relationship. Alternatively, one can develop custom serialization code that ignore any such bidirectional relationship or circular dependency in the data.

But we don’t want to ignore or omit either side of the bidirectional relationship. We want to preserve it, in both directions, without generating any errors. A real solution should allow circular dependencies in JSON and allow the developer to stop thinking about them without taking additional actions to fix them. This article provides a practical and straightforward technique for doing so, which can serve as a useful addition to any standard set of tips and practices for today’s front-end developer.

A Simple Bidirectional Relationship Example

A common case where this bidirectional relationship (a.k.a. circular dependency) issue arises is when there is a parent object that has children (which it references) and those child objects, in turn, want to maintain references to their parent. Here’s a simple example:

var obj = {
	"name": "I'm parent"
}

obj.children = [
	{
		"name": "I'm first child",
		"parent": obj
	},
	{
		"name": "I'm second child",
		"parent": obj
	}
]

If you try to convert the above parent object to JSON (for example, by using the stringify method, as in var parentJson = JSON.stringify(parent);), the exception Uncaught TypeError: Converting circular structure to JSON will be thrown.

While we could use one of the techniques discussed above (such as using annotations like @JsonIgnore), or we could simply remove the above references to the parent from the children, these are ways of avoidingrather than solving the problem. What we really want is a resulting JSON structure that maintains each bidirectional relationship and that we can convert to JSON without throwing any exceptions.

Moving Toward a Solution

One potentially obvious step toward a solution is to add some form of object ID to each object and then replace the children’s references to the parent object with references to the parent object’s id. For example:

var obj = {
	"id": 100,
	"name": "I'm parent"
}

obj.children = [
	{
		"id": 101,
		"name": "I'm first child",
		"parent": 100
	},
	{
		"id": 102,
		"name": "I'm second child",
		"parent": 100
	}
]

This approach will certainly avoid any exceptions that result from a bidirectional relationship or circular reference. But there’s still an issue, and that issue becomes apparent when we think about how we would go about serializing and deserializing these references.

The issue is that we would need to know, using the above example, that every reference to the value “100” refers to the parent object (since that’s its id). That will work just fine in the above example where the only property that has the value “100” is the parent property. But what if we add another property with the value “100”? For example:

obj.children = [
	{
		"id": 101,
		"name": "I'm first child",
        "priority": 100,  // This is NOT referencing object ID "100"
		"parent": 100     // This IS referencing object ID "100"
	},
	{
		"id": 102,
		"name": "I'm second child",
        "priority": 200,
		"parent": 100
	}
]

If we assume that any reference to the value “100” is referencing an object, there will be no way for our serialization/deserialization code to know that when parent references the value “100”, that IS referencing the parent object’s id, but when priority references the value “100”, that is NOT referencing the parent object’s id (and since it will think that priority is also referencing the parent object’s id, it will incorrectly replace the its value with a reference to the parent object).

You may ask at this point, “Wait, you’re missing an obvious solution. Instead of using the property value to determine that it’s referencing an object id, why don’t you just use the property name?” Indeed, that is an option, but a very limiting one. It will mean that we will need to predesignate a list of “reserved” property names that are always assumed to reference other objects (names like “parent”, “child”, “next”, etc.). This will then mean that only those property names can be used for references to other objects and will also mean that those property names will always be treated as references to other objects. This is therefore not a viable alternative in most situations.

So it looks like we need to stick with recognizing property values as object references. But this means that we will need these values to be guaranteed to be unique from all other property values. We can address the need for unique values by using Globally Unique Identifiers (GUIDs). For example:

var obj = {
	"id": "28dddab1-4aa7-6e2b-b0b2-7ed9096aa9bc",
	"name": "I'm parent"
}

obj.children = [
	{
		"id": "6616c598-0a0a-8263-7a56-fb0c0e16225a",
		"name": "I'm first child",
        "priority": 100,
		"parent": "28dddab1-4aa7-6e2b-b0b2-7ed9096aa9bc" // matches unique parent id
	},
	{
		"id": "940e60e4-9497-7c0d-3467-297ff8bb9ef2",
		"name": "I'm second child",
        "priority": 200,
		"parent": "28dddab1-4aa7-6e2b-b0b2-7ed9096aa9bc" // matches unique parent id
	}
]

So that should work, right?

Yes.

But…

A Fully Automated Solution

Remember our original challenge. We wanted to be able to serialize and deserialize objects that have a bidirectional relationship to/from JSON without generating any exceptions. While the above solution accomplishes this, it does so by requiring us to (a) add some form of unique ID field to each object and (b)replace each object reference with the corresponding unique ID. This will work, but we’d much prefer a solution that would just automatically work with our existing object references without requiring us to “manually” modify our objects this way.

Ideally, we want to be able to pass a set of objects (containing any arbitrary set of properties and object references) through the serializer and deserializer (without generating any exceptions based on a bidirectional relationship) and having the objects generated by the deserializer precisely match the objects that were fed into the serializer.

Our approach is to have our serializer automatically create and add a unique ID (using a GUID) to each object. It then replaces any object reference with that object’s GUID. (Note that the serializer will need to use some unique property name for these IDs as well; in our example, we use @id since presumably prepending the “@” to the property name is adequate to ensure that it is unique.) The deserializer will then replace any GUID that corresponds to an object ID with a reference to that object (note that the deserializer will also remove the serializer-generated GUIDs from the deserialized objects, thereby returning them precisely to their initial state).

So returning to our example, we want to feed the following set of objects as is to our serializer:

var obj = {
	"name": "I'm parent"
}

obj.children = [
	{
		"name": "I'm first child",
		"parent": obj
	},
	{
		"name": "I'm second child",
		"parent": obj
	}
]

We would then expect the serializer to generate a JSON structure similar to the following:

{
	"@id": "28dddab1-4aa7-6e2b-b0b2-7ed9096aa9bc",
	"name": "I'm parent",
	"children": [
		{
		    "@id": "6616c598-0a0a-8263-7a56-fb0c0e16225a",
			"name": "I'm first child",
			"parent": "28dddab1-4aa7-6e2b-b0b2-7ed9096aa9bc"
		},
		{
		    "@id": "940e60e4-9497-7c0d-3467-297ff8bb9ef2",
			"name": "I'm second child",
			"parent": "28dddab1-4aa7-6e2b-b0b2-7ed9096aa9bc"
		},
	]
}

Then feeding the above JSON to the deserializer would generate the original set of objects (i.e., the parent object and its two children, referencing one another properly).

So now that we know what we want to do and how we want to do it, let’s implement it.

Implementing the Serializer in JavaScript

Below is a sample working JavaScript implementation of a serializer that will properly handle a bidirectional relationship without throwing any exceptions.

var convertToJson = function(obj) {

    // Generate a random value structured as a GUID
    var guid = function() {
        function s4() {
            return Math.floor((1 + Math.random()) * 0x10000).toString(16).substring(1);
        }

        return s4() + s4() + '-' + s4() + '-' + s4() + '-' + s4() + '-' + s4() + s4() + s4();
    };

    // Check if a value is an object
    var isObject = function(value) {
        return (typeof value === 'object');
    }
    
    // Check if an object is an array
    var isArray = function(obj) {
        return (Object.prototype.toString.call(obj) === '[object Array]');
    }
    
    var convertToJsonHelper = function(obj, key, objects) {
        // Initialize objects array and 
        // put root object into if it exist
        if(!objects) {
            objects = [];
    
            if (isObject(obj) && (! isArray(obj))) {
                obj[key] = guid();
                objects.push(obj);
            }
        }
    
        for (var i in obj) {
            // Skip methods
            if (!obj.hasOwnProperty(i)) {
                continue;
            }
    
            if (isObject(obj[i])) {
                var objIndex = objects.indexOf(obj[i]);
    
                if(objIndex === -1) {
                    // Object has not been processed; generate key and continue
                    // (but don't generate key for arrays!)
                    if(! isArray(obj)) {
                        obj[i][key] = guid();
                        objects.push(obj[i]);
                    }
 
                    // Process child properties
                    // (note well: recursive call)
                    convertToJsonHelper(obj[i], key, objects);
                } else {
                    // Current object has already been processed;
                    // replace it with existing reference
                    obj[i] = objects[objIndex][key];
                }
            }
        }
    
        return obj;
    }

    // As discussed above, the serializer needs to use some unique property name for
    // the IDs it generates. Here we use "@id" since presumably prepending the "@" to
    // the property name is adequate to ensure that it is unique. But any unique
    // property name can be used, as long as the same one is used by the serializer
    // and deserializer.
    //
    // Also note that we leave off the 3rd parameter in our call to
    // convertToJsonHelper since it will be initialized within that function if it
    // is not provided.
    return convertToJsonHelper(obj, "@id");
}

Fast & Reliable Cloud Backups

For MySQL, MongoDB, Linux, Unix

Get Started