AnyWhichWay
Cycler ... cycle.js revisted

Home Cycler ... cycle.js revistied. Re-factoring and enhancing an old stand-by. February 24st, 2016

In order to serialize JavaScript objects they often need to have circular references removed. The most popular package for accomplishing this appears to be cycle.js, the stats for which are below:

This is undoubtedly a tried and true codebase with lots of current interest, despite the amazing lack of stars in either GitHub or NPM. However, the codebase is not actively maintained to take advantage of enhancements to JavaScript or provide for the evolving needs of newer JavaScript client and server based applications. The most recent commit is Apr 26, 2014 and some of the repository has not been touched since Dec 16, 2013.

In this article we revisit cycle.js and discuss several modifications in the context of efficiency, code quality, functionality, and packaging. Although these modifications are relatively minor in the context of cycle.js, they illustrate the types of changes that could be made to other code bases.

The end result is a package, cycler.js, that can be used to support more efficient and accurate isomorphic programming. The cycler.js npm package also include unit tests.

So long as the same constructors are available in the serializing and de-serializing environments, cycler.js ensures that functional semantics follow along with data as it is transmitted or stored and restored.

When reading this article, it will be useful to have a line numbered version of the legacy source available.

Efficiency

Starting at line 64 of cycle.js, the below can be found:

// If the value is an object or array, look to see if we have already
// encountered it. If so, return a $ref/path object. This is a hard way,
// linear search that will get slower as the number of unique objects grows.

for (i = 0; i < objects.length; i += 1) {
    if (objects[i] === value) {
        return {$ref: paths[i]};
    }
}

Updating the code to use a Map eliminates much of the scaling issue. The can be done by initializing the objects variable on line 43 of the original code with a Map and replacing the code starting at line 67 through 71 with the below

pathfound = objects.get(value);
   if(pathfound) {
       return {$ref: pathfound};
   }

And a replacement of lines 76, 77 with:

objects.set(value,path);

Code Quality

Newer versions of JavaScript engines allow us to reduce the complexity of code and make our intent clear when doing things that might be otherwise thought of as suspicious, e.g. use of eval or for(var ... in) without loop checks.

Complexity

Starting on line 139 of the original code the following can be found:

if (value && typeof value === 'object') {
    if (Object.prototype.toString.apply(value) === '[object Array]') {
        for (i = 0; i < value.length; i += 1) {
            item = value[i];
            if (item && typeof item === 'object') {
                path = item.$ref;
                if (typeof path === 'string' && px.test(path)) {
                    value[i] = eval(path);
                } else {
                    rez(item);
                }
            }
        }
    } else {
        for (name in value) {
            if (typeof value[name] === 'object') {
                item = value[name];
                if (item) {
                    path = item.$ref;
                    if (typeof path === 'string' && px.test(path)) {
                        value[name] = eval(path);
                    } else {
                        rez(item);
                    }
                }
            }
        }
    }
}

Since array items are just indexed keys, the above can be replaced with a forEach call:

Object.keys(value).forEach(
	function(name) {
		var item = value[name];
		if (item && typeof item === "object"
				&& typeof item.$ref === "string"
				&& px.test(item.$ref)) {
			value[name] = eval(item.$ref);
		} else if (item && typeof item === "object") {
			rez(item);
		}
	});

This is not only less complex, it is half the size. Also note the use of the same initial tests, item && typeof item === "object" in the if else if. By not using a wrapping conditional so there is only one occurrence of typeof item === "object", the number of code branches and complexity are reduced. For a small function where the chance of additional changes in the future is low, this is OK. However, for a large conditional with multiple branches this would probably make code more fragile and obscure.

With a variable declaration change to line 52:

nu = (Array.isArray(value) || value instanceof Array ? [] : {});

Similar changes can be made to the code starting at line 81

Object.keys(value).forEach(function(key) {
	nu[key] = derez(value[key], path + "[" + (Array.isArray(nu) ? key : JSON.stringify(key)) + "]");
});

Security

Most code quality checkers flag the use of eval. Although they can still create security issues, the construction of dynamic functions at least has the programmer be more thoughtful. The remaining eval call in the above complexity reduction code can be replaced with a dynamic function Function("dollar","var $ = dollar; return " + item.$ref)($):

Object.keys(value).forEach(
	function(name) {
		var item = value[name];
		if (item && typeof item === "object"
				&& typeof item.$ref === "string"
				&& px.test(item.$ref)) {
			value[name] = Function("dollar","var $ = dollar; return " + item.$ref)($);
		} else if (item && typeof item === "object") {
			rez(item);
		}
	});

Functionality

The original code assumes:

  1. Array's are never sub-classed with respect to objects to be decycled.
  2. All objects should be restored as POJOs or Arrays when retrocycled/restored.

Improved Array Handling

On lines 81 and 140 of the original code the following appears:

if(Object.prototype.toString.apply(value) === '[object Array]') { ...

This will not properly handle situations in which Array has been sub-classed since the toString function will not return [object Array] for instances of the sub-class. Theoretically, the fix is easy!

if(Array.isArray(value)) { ...

However, our unit tests in Chrome fail unless we also do an instanceof check when using sub-classed arrays.

if(Array.isArray(value) || value instanceof Array) { ...

Packaging

Re-packaging simply takes the form of renaming cycle.js to index.js and creating a browser directory for browserified and pre-minified versions of the code. As is expected of modern packages, unit tests runable in either the browser or in a build environment are added in a test directory. Finally, since some organizations do not allow the use of code un-associated with some type of license, a permissive MIT license is added. All of these require updates to package.json but the mechanics are beyond the scope of this article. The reader is simply invited compare the original package.json to the one associated with cycler.js.

Beyond POJOs

The primary use case for decycling and retrocycling JavaScript objects is to support serialization as JSON, often for transfer to a server. JSON provides no standard means for representing anything other than Object and Array data; however, it would be useful to transfer more semantics. And, inserting functional code into JSON would both introduce security risks and size bloat. So, what are we do to if we wish to leverage isomorphic programming?

It turns out that some straightforward enhancements to cycle.js will allow us to address this issue in an un-obtrusive and relatively concise manner. While an object is being traversed to replace cyclic references with JSONPath expressions, the specific class of each object can be captured and saved as an extra element in the JSON. When the process is being reversed this data can be used to select a constructor in the target restoration environment to re-create each object.

Although not complex, the nature of these enhancements does not lend itself well to the line by line approach have taken up to this point, particularly since so much code has been modified already. Hence, most of the the commentary will be more general in nature. First, we need to answer a few design questions.

  1. How do we know to what class objects should be restored and how do we capture that? We add a property to the object that only exists while the object is decycled. We store the class name in string property. Just about any property name that is not likely to collide with an existing object property will do, for Cycler the property $class is used. But what do we do about Arrays, since they do not have anything other than their elements saved in JSON? We can add a special single property object as the last element in each Array. For Cycler, the single property is, you probably guessed it, $class. This element also only exists while an array is decycled.
  2. Where do we get the class names? Let's assume that the application is using well patterned classes and instances where the built-in .constructor property on each instance links to the function which defines the class. This makes getting a class name as simple as referencing .constructor.name. But what do we do in cases where functions are anonymous or the JavaScript engine does not support named functions (e.g. Internet Explorer)? We can augment the .decycle and .retrocycle functions to take a context object, the keys of which are class names with values as constructor functions. The keys of this context object can then be walked to find values where context[key] === .constructor. When this is true, the key is the class name. In most cases,the context argument will no tbe needed.
  3. What should we do if $class is not available as a constructor in the target restoration environment? We should just return a POJO like the original cycle.js code would have done anyway.

The above decisions in place, we can write a function that isolates new code to support decycling and retrocycling:

function augment(context, original, decycled) {
	var classname = original.constructor.name;
	if (!classname || classname === "") { // look in context if classname not available
		Object.keys(context).some(function(name) {
			if (context[name] === original.constructor) {
				classname = name;
				return true;
			}
		});
	}
	if (classname && classname.length > 0) { // add the $class info to array or object
		if (Array.isArray(decycled)) {
			decycled.push({
				$class : classname
			});
			return;
		}
		decycled.$class = classname;
	}
}

We can insert augment calls after the code we inserted at the original line 81.

Object.keys(value).forEach(function(key) {
	nu[key] = derez(value[key], path + "[" + (Array.isArray(nu) ? key : JSON.stringify(key)) + "]");
});
augment(context, value, nu); 

We also need functions to help us resurrect objects. We could do this all in one function, but that would results in high complexity, so we create two. The first is a support function, getConstructor that knows how to get a constructor based on its name from constructors or the restoration context. The second, resurrect, does the heavy lifting.

function getConstructor(context,item) {
	var obj; // temporary variable
	// process objects and return possibly modified item
	if (item && item.$class) {
		if(typeof (context[item.$class]) === "function") {
			return context[item.$class];
		}
		delete item.$class;
	}
	if (Array.isArray(item) && item[item.length - 1].$class
			&& Object.keys(item[item.length - 1]).length === 1) {
		if(typeof (context[item[item.length - 1].$class]) === "function") {
			return context[item[item.length - 1].$class];
		}
		// otherwise delete the $class data
		item.splice(item.length - 1, 1);
	}
	return undefined;
}

function resurrect(context, item) {
	var obj, // temporary variable
		cons = getConstructor(context,item)
	// process objects and return possibly modified item
	if (cons) {
		obj = Object.create(cons.prototype);
		obj.constructor = cons;
		Object.keys(item).forEach(function(key,i) {
			if (key !== "$class" && (i!==item.length-1 || !(Array.isArray(item) || item instanceof Array))) { // skip the $class data
				obj[key] = item[key];
			}
		});
		return obj;
	}
	return item;
}

We can insert calls to resurrect in the new complexity reduction code we introduced early in the article:

Object.keys(value).forEach(
	function(name) {
		var item = resurrect(context, value[name]);
		value[name] = item; // re-assign in case item has been converted
		if (item && typeof item === "object"
				&& typeof item.$ref === "string"
				&& px.test(item.$ref)) {
			value[name] = Function("dollar","var $ = dollar; return " + item.$ref)($);
		} else if (item && typeof item === "object") {
			rez(item);
		}
	});

Conclusion

By applying modern JavaScript techniques to an older code base we have decreased its complexity, theoretically improved its performance (yet to be tested) and increased its utility for modern applications albeit with an increase in size.

The legacy source has 79 lines of code and minified is 1.49K. The new source has 140 lines of code and minified is 2.48K, but would have been far larger without the use of forEach. The application of just forEach to the legacy code would reduce its line count to 52 and its size to 1.11K. The un-minified size is not compared since it penalizes the use of comments.

The legacy source has two functions with moderately high complexity, derez at 8 and rez at 10. The average function complexity is 3.75. The two highest complexity functions in the new source are, augment and getConstructor at 5. The average function complexity is 2.6.

Cycler.js is available at https://github.com/anywhichway/cycler

Copyright 2016, AnyWhichWay