My JavaScript book is out! Don't miss the opportunity to upgrade your beginner or average dev skills.

Tuesday, February 14, 2012

JSON.stringify Recursion + Max Execution Stack Exceeded

I believe this is a common problem, and we had a similar one today while debugging.
JSON methods do not support recursion ... which is the only thing I am really missing back to PHP serialize days.

Recursion Is Bad

Well, I would say cyclic references are never that good but sometimes these may happen and, specially while testing and debugging, it's more than useful to understand what happened there.
If you have cyclic/cross references in your code I suggest you to use approaches which aim is to avoid these kind of direct links.
Harmony Collections, specially Map and WeakMap, are indeed good helpers to reference indirectly objects without creating, hopefully, first level links and/or recursions.

How To Serialize Anyway

JSON.stringify() accepts a second argument called replacer.
I won't explain more than MDN about its potentials, but it can be really handy to avoid recursions.
A simple way to do it is indeed to store in a stack already parsed objects, included the object itself.
Some other extra operation may be handy too so the debug will be as complete as possible.

var replacer = function (stack, undefined, r, i) {
// a WebReflection hint to avoid recursion
return function replacer(key, value) {
// this happens only first iteration
// key is empty, and value is the object
if (key === "") {
// put the value in the stack
stack = [value];
// and reset the r
r = 0;
return value;
}
switch(typeof value) {
case "function":
// not allowed in JSON protocol
// let's return some info in any case
return "".concat(
"function ",
value.name || "anonymous",
"(",
Array(value.length + 1).join(",arg").slice(1),
"){}"
);
// is this a primitive value ?
case "boolean":
case "number":
case "string":
// primitives cannot have properties
// so these are safe to parse
return value;
default:
// only null does not need to be stored
// for all objects check recursion first
// hopefully 255 calls are enough ...
if (!value || !replacer.filter(value) || 255 < ++r) return undefined;
i = stack.indexOf(value);
// all objects not already parsed
if (i < 0) return stack.push(value) && value;
// all others are duplicated or cyclic
// mark them with index
return "*R" + i;
}
};
}();

// reusable to filter some undesired object
// as example HTML node
replacer.filter = function (value) {
// i.e. return !(value instanceof Node)
// to ignore nodes
return value;
};

A simple example about above function could be this one:

// how to test it
var o = {a:[], b:123, c:{}, e:function test(a,b){}};
o.d = o;
o.a.push(o);
o.c.o = o;
o.c.a = o.a;
o.c.c = o.c;
o.a.push(o.c);
alert(JSON.stringify(o, replacer));

Above alert will produce this kind of output:
{"a":["*R0",{"o":"*R0","a":"*R1","c":"*R2"}],"b":123,"c":"*R2","e":"function test(arg,arg){}","d":"*R0"}
which is surely not as bad as an exception, isn't it?

The Max Execution Stack Problem

Even using a stack variable, in order to avoid duplicated entries, the reason 255 < ++r is necessary is that the generic object may reference in one or more properties a DOM node.
Specially in big applications, the number of nodes, all unique, could be able to reach the function limit.
A tricky way to know this limit, which is browser and engine dependent, could be this one:

(function (Function, MAX_EXECUTION_STACK) {
if (MAX_EXECUTION_STACK in Function) return;
Function[MAX_EXECUTION_STACK] = function (i) {
try {
(function max(){
++i && max();
}());
} catch(o_O) {
return i;
}
}(0);
}(Function, "MAX_EXECUTION_STACK"));

// browser dependent
alert(Function.MAX_EXECUTION_STACK);

Unfortunately in the replacer we cannot use this number in any case because we don't know how many other times the function itself will be called but a good compromise, able to generate objects almost impossible to debug, would be Function.MAX_EXECUTION_STACK / 100 so the limit will scale accordingly.
In all other situations where we still have recursion and max execution stack problems but we are those calling our own function, this limit could be more than handy, i.e.

var
i = 0,
fn = function (obj) {
for (var key in obj) {
if (++i < Function.MAX_EXECUTION_STACK) {
parse(obj[key]);
fn(obj[key]);
}
}
}
;

... so now you know ...

No comments: