I am trying to learn recursion in Javascript, so I figured I'd rewrite the native JSON.stringify function using recursion as a challenge to myself. I almost got my code to work:
var my_stringify = function(obj){
value = obj[ Object.keys(obj)[0] ];
index = Object.keys(obj)[0];
delete obj[ Object.keys(obj)[0] ];
// The value is just a simple string, not a nested object
if (typeof value === 'string'){
if (Object.keys(obj).length !== 0){
// Continue recursion ..
return '"' + index + '":"' + value + '",' + my_stringify(obj);
}
// This would be the base case with a string at the end. Stop recursion.
return '"' + index + '":"' + value + '"}';
}
// The value is actually a nested object
else{
if (Object.keys(obj).length !== 0){
// Continue recursion ..
return '"' + index + '":{' + my_stringify(value) + ',' + my_stringify(obj);
}
// This is the base case with a nested object at the end. Stringify it and end recursion.
return '"' + index + '":{' + my_stringify(value) + '}';
}
}
Except for the fact that the first { in my answer is missing, and I can't figure out how to fix this bug.
E.g. my_stringify({foo: 'bar'}) returns "foo":"bar"} instead of {"foo":"bar"}.
Also, I'm aware I'm completely destroying the original object, is there any way to send over to recursion a reduced version of the original object without deleting anything (something like obj.slice(1))?
Any advice will be greatly appreciated !
8 Answers 8
2024, type safe
This updated version is type safe and handles function, symbol, and bigint types -
function stringifyJSON(t: unknown): undefined | string {
if (t === undefined) return undefined
else if (t === null) return 'null'
else if (typeof t == 'bigint') throw TypeError('stringifyJSON cannot serialize BigInt')
else if (typeof t == 'number') return String(t)
else if (typeof t == 'boolean') return t ? 'true' : 'false'
else if (typeof t == 'string') return '"' + t.replace(/"/g, '\\"') + '"'
else if (typeof t == 'object') return Array.isArray(t)
? '[' + Array.from(t, v => stringifyJSON(v) ?? 'null').join(',') + ']'
: '{' + Object.entries(t)
.map(([k,v]) => [stringifyJSON(k), stringifyJSON(v)])
.filter(([k,v]) => v !== undefined)
.map(entry => entry.join(':'))
.join(',') + '}'
else return undefined
}
2024, circular reference check
This updated version throws an error when a circular object reference is used -
function stringifyJSON(t: unknown, seen: Set<unknown> = new Set()): undefined | string {
if (seen.has(t)) throw TypeError('stringifyJSON cannot serialize cyclic structures')
else if (t === undefined) return undefined
else if (t === null) return 'null'
else if (typeof t == 'bigint') throw TypeError('stringifyJSON cannot serialize BigInt')
else if (typeof t == 'number') return String(t)
else if (typeof t == 'boolean') return t ? 'true' : 'false'
else if (typeof t == 'string') return '"' + t.replace(/"/g, '\\"') + '"'
else if (typeof t == 'object') {
const nextSeen = new Set(seen).add(t)
return Array.isArray(t)
? '[' + Array.from(t, v => stringifyJSON(v, nextSeen) ?? 'null').join(',') + ']'
: '{' + Object.entries(t)
.map(([k,v]) => [stringifyJSON(k, nextSeen), stringifyJSON(v, nextSeen)])
.filter(([k,v]) => v !== undefined)
.map(entry => entry.join(':'))
.join(',') + '}'
}
else return undefined
}
2017, new answer to an old question
There's some painfully bad answers here that fail under even the simplest examples. This answer aims to answer the question exhaustively and demonstrate how an approach like this scales even when handling a wide variety of data types and ...
Corner cases
This function does a simple case analysis on a non-null data's constructor property and encodes accordingly. It manages to cover a lot of corner cases that you're unlikely to consider, such as
JSON.stringify(undefined)returnsundefinedJSON.stringify(null)returns'null'JSON.stringify(true)returns'true'JSON.stringify([1,2,undefined,4])returns'[1,2,null,4]'JSON.stringify({a: undefined, b: 2})returns'{ "b": 2 }'JSON.stringify({[undefined]: 1})returns'{ "undefined": 1 }'JSON.stringify({a: /foo/})returns{ "a": {} }
So to verify that our stringifyJSON function actually works properly, I'm not going to test the output of it directly. Instead, I'm going to write a little test method that ensures the JSON.parse of our encoded JSON actually returns our original input value
// we really only care that JSON.parse can work with our result
// the output value should match the input value
// if it doesn't, we did something wrong in our stringifier
const test = data => {
return console.log(JSON.parse(stringifyJSON(data)))
}
test([1,2,3]) // should return [1,2,3]
test({a:[1,2,3]}) // should return {a:[1,2,3]}
Disclaimer: it should be obvious that the code I'm about to share is not meant to be used as an actual replacement for
JSON.stringify– there's countless corner cases we probably didn't address. Instead, this code is shared to provide a demonstration for how we could go about such a task. Additional corner cases could easily be added to this function.
Runnable demo
Without further ado, here is stringifyJSON in a runnable demo that verifies excellent compatibility for several common cases
const stringifyJSON = data => {
if (data === undefined)
return undefined
else if (data === null)
return 'null'
else if (data.constructor === String)
return '"' + data.replace(/"/g, '\\"') + '"'
else if (data.constructor === Number)
return String(data)
else if (data.constructor === Boolean)
return data ? 'true' : 'false'
else if (data.constructor === Array)
return '[ ' + data.reduce((acc, v) => {
if (v === undefined)
return [...acc, 'null']
else
return [...acc, stringifyJSON(v)]
}, []).join(', ') + ' ]'
else if (data.constructor === Object)
return '{ ' + Object.keys(data).reduce((acc, k) => {
if (data[k] === undefined)
return acc
else
return [...acc, stringifyJSON(k) + ':' + stringifyJSON(data[k])]
}, []).join(', ') + ' }'
else
return '{}'
}
// round-trip test and log to console
const test = data => {
return console.log(JSON.parse(stringifyJSON(data)))
}
test(null) // null
test('he said "hello"') // 'he said "hello"'
test(5) // 5
test([1,2,true,false]) // [ 1, 2, true, false ]
test({a:1, b:2}) // { a: 1, b: 2 }
test([{a:1},{b:2},{c:3}]) // [ { a: 1 }, { b: 2 }, { c: 3 } ]
test({a:[1,2,3], c:[4,5,6]}) // { a: [ 1, 2, 3 ], c: [ 4, 5, 6 ] }
test({a:undefined, b:2}) // { b: 2 }
test({[undefined]: 1}) // { undefined: 1 }
test([[["test","mike",4,["jake"]],3,4]]) // [ [ [ 'test', 'mike', 4, [ 'jake' ] ], 3, 4 ] ]3 Comments
if (data[k] === undefined) return acc to if (data[k] === undefined || data[k] === data) return acc to avoid recursive calls in case the object has a circular reference. Example: window, global.You need to view recursion as going deeper into the object without actually altering the object. It looks like you're trying to use recursion to go sideways inside of an object.
I've written a version of stringify that handles basic object (no arrays or functions).
Here is the fiddle
Here is the code:
var my_stringify2 = function (obj) {
var objKeys = Object.keys(obj);
var keyValueArray = new Array();
for (var i = 0; i < objKeys.length; i++) {
var keyValueString = '"' + objKeys[i] + '":';
var objValue = obj[objKeys[i]];
keyValueString = (typeof objValue == "string") ?
keyValueString = keyValueString + '"' + objValue + '"' :
keyValueString = keyValueString + my_stringify2(objValue);
keyValueArray.push(keyValueString);
}
return "{" + keyValueArray.join(",") + "}";
}
You want the recursion to do most of the work for you, and you should only need to handle basic conditions (which you already had). In my function the two acceptable conditions are string and object.
A string is handled on the spot, and an object is passed into the function recursively.
That's the key. You were passing the same object into the function repeatedly, removing the handled elements until you get to a point where the object is completely gone.
What I did instead was pass the value of that particular property if it were an object. If it's a string, just add it to the string and move along.
Take a look at the code and let me know if you have any questions. Notice that the object that I'm passing in has a nested object.
my_stringify2({
foo: 'bar',
bar: 'foo',
foobar: {
foo: 'bar',
bar: 'foo'
}
});
and the result is proper json
{"foo":"bar","bar":"foo","foobar":{"foo":"bar","bar":"foo"}}
If you're looking to completely avoid a for loop, you can do the following
in this one you pass the object like normal, but recursively you pass a key array, removing an element from the key array for each property.
a bit more complicated, so I added comments
var my_stringify2 = function (obj, objKeys) {
var str = "";
// keys haven't been loaded, either first pass, or processing a value of type object
if (objKeys == undefined) {
objKeys = Object.keys(obj);
str = "{"
} else {
// if keys array exists and is empty, no more properties to evaluate, return the end bracket
if (objKeys.length == 0) {
return "}";
// array exists and isn't empty, that means it's a property and not the first property, add a comma
} else {
str = ",";
}
}
// add the property name
str += '"' + objKeys[0] + '":';
// get the value
var objValue = obj[objKeys[0]];
// if the value type is string, add the string, if it's an object, call this function again, but leave the objKeys undefined
str +=
(typeof objValue == "string") ?
'"' + objValue + '"' :
my_stringify2(objValue);
// remove the first element fromt the keys array
objKeys.splice(0,1);
//call the function for the next property
return str + my_stringify2(obj, objKeys);
}
2 Comments
{"foo": true, "bar": false, "baz": null}This has been answered several times but here is yet another solution:
Using es6:
let oldStringify = JSON.stringify;
JSON.stringify = (obj, replacer, space) => oldStringify(obj, replacer || ((key, value) => {if(key && value === obj) return "[recursive]"; return value;}), space)
1 Comment
eventI was asked this in an Interview question and this is what I came up with. An understandable recursive approach:
function stringify(input) {
var arrVals = [];
Object.keys(input).forEach(function(keyName) {
let val = input[keyName];
if (typeof val !== 'undefined' && typeof val !== 'function') {
arrVals.push(getQuotedString(keyName) + ":" + getString(val));
}
});
return '{' + arrVals.join(',') + '}';
}
function getString(val) {
switch (typeof val) {
case 'string':
return getQuotedString(val);
break;
case 'number':
case 'boolean':
return val;
break;
case 'object':
if (val === null) {
return "null";
}
if (Array.isArray(val)) {
let arrString = []
for (let i = 0; i < val.length; i++) {
arrString.push(getString(val[i]));
}
return "[" + arrString.join(',') + "]";
}
return stringify(val);
break;
}
}
function getQuotedString(str) {
return '"' + str + '"';
}Test using following obj:
var input = {
"a": 1,
"b": 'text',
"c": {
"x": 1,
"y": {
"x": 2
}
},
"d": false,
"e": null,
"f": undefined,
"g": [1, "text", {
a: 1,
b: 2
}, null]
};1 Comment
Here is an implementation that follows the ECMA Script specification (excluding extra arguments that can be passed to JSON.stringify):
function stringifyJSON(value) {
const charMap = { "\b": "\\b", "\t": "\\t", "\n": "\\n", "\f": "\\f",
"\r": "\\r", '"': '\\"', "\\": "\\\\" };
const stack = new Set;
const stringToJson = value =>
'"' + value.replace(/[\x00-\x1F"\\\uD800-\uDFFF]/gu, c =>
charMap[c] ?? `\\u${c.charCodeAt().toString(16).padStart(4, "0")}`
) + '"';
const objectToJson = obj =>
`{${Object.entries(obj).map(([key, value]) => {
value = anyToJson(value);
if (value !== undefined) return `${stringToJson(key)}:${value}`;
}).filter(Boolean)}}`;
const arrayToJson = arr =>
`[${Array.from(arr, value => {
value = anyToJson(value);
return value === undefined ? "null" : value;
})}]`;
function anyToJson(value) {
// Support for toJSON method
if (typeof Object(value).toJSON === "function") value = value.toJSON();
// Unwrap boxed primitives
if (value instanceof Number || value instanceof String
|| value instanceof Boolean || value instanceof BigInt) {
value = value.valueOf();
}
// Primitive values:
const typ = typeof value;
if (typ === "bigint") throw new TypeError("Do not know how to serialize a BigInt");
if (typ === "boolean" || value === null) return String(value);
if (typ === "number") return (Number.isFinite(value) ? String(value) : "null");
if (typ === "string") return stringToJson(value);
if (typ !== "object") return;
// (non-callable) object:
if (stack.has(value)) throw new TypeError("Converting circular structure to JSON");
stack.add(value);
const result = Array.isArray(value) ? arrayToJson(value, stack)
: objectToJson(value, stack);
stack.delete(value);
return result;
}
return anyToJson(value);
}
// Test
BigInt.prototype.toJSON = () => "I'm a BigInt";
const o = {
"!è#": `
a\r
b\t
c`,
"😀": "-🤣-",
a: [NaN, Infinity, -Infinity, 3.14e48, undefined, null, () => {}, Symbol.iterator],
b: [],
c: [new Number(8), new String("ok"), new Boolean(false)],
d: () => {},
e: Object.assign(Object(12n), { toJSON: () => "hello" }),
f: Object(Symbol.iterator),
g: 12n
};
console.log(stringifyJSON(o) === JSON.stringify(o)); // trueNotably, it implements the following specifics:
- If the object to serialize has a
toJSONmethod, it is called - If a cyclic reference is detected, a TypeError is thrown
- Non-finite numbers result in "null" (this is the case for
NaN,-Infinity,Infinity) - Control characters, double quote and backslash characters are escaped
- Function objects and Symbol primitives result in undefined
- If the object is a primitive-wrapper object (instance of
Number,String,BigInt,Boolean, possibly sub classed), the primitive value is taken instead - Undefined values (after applying above rules) are omitted from object serialization and are rendered as "null" when they occur in arrays.
Comments
Fundamentally, you are stringifying by cutting off the first property, stringifying that and then recursing of the rest of the object. IMHO this is not the way to go, the only reason to recurse is when there is a nested object, otherwise you should just iterate through the properties. As you've done it, you've made it much more difficult to tell if you are at the beginning of the object and should return that missing { with your string.
In semi-pseudo code (leaving you some work to do yourself), you want something like this:
var my_stringify = function(obj) {
// check first for null / undefined / etc and return
var myJSON = "{";
// iterate through all the properties of the object
for (var p in obj) {
if (obj.hasOwnProperty(p)) {
// check to see if this property is a string, number, etc
if (//...) {
myJSON += // the JSON representation of this value using p and obj[p]
}
if (// test for nested object) {
myJSON += my_stringify(obj[p]); // this is recursion!
}
if (// test for arrays) {
// arrays also need special handling and note that they might
// include objects or other arrays - more chances for recursion!
}
// note: functions should be ignored, they aren't included in JSON
}
}
return myJSON + "}";
}
1 Comment
I disagree with @Bergi's assertion that regular old recursion isn't a good fit for this. Like I said in my comment you can avoid the use of a for loop by passing the index as an argument to the function. This is a very common technique and prevents you from needing to copy or modify the data structure.
Here's my stab at such an implementation. As you can see it's really straightforward (and to my own surprise, it works!):
function jsonify(obj, idx) {
var json, objStr = toString.call(obj);
// Handle strings
if(objStr == '[object String]') { return '"' + obj + '"' }
idx = idx || 0
// Handle arrays
if(objStr == '[object Array]') {
if(idx >= obj.length) {
// The code below ensures we'll never go past the end of the array,
// so we can assume this is an empty array
return "[]"
}
// JSONify the value at idx
json = jsonify( obj[idx] )
if(idx < obj.length - 1) {
// There are items left in the array, so increment the index and
// JSONify the rest
json = json + "," + jsonify( obj, idx + 1 )
}
// If this is the first item in the array, wrap the result in brackets
if(idx === 0) { return "[" + json + "]" }
return json
}
// Handle objects
if(obj === Object(obj)) {
var keys = Object.keys(obj)
var key = keys[idx]
// JSONify the key and value
json = '"' + key + '":' + jsonify( obj[key] )
if(idx < keys.length - 1) {
// There are more keys, so increment the index and JSONify the rest
return json + "," + jsonify( obj, idx + 1 )
}
// If this is the first key, wrap the result in curly braces
if(idx === 0) { return "{" + json + "}" }
return json
}
return obj.toString() // Naively handle everything else
}
var items = [ 9, "nine", { "key": [], "key2": { "subkey": 3.333 } } ]
console.log("OUTPUT", jsonify(items))
// => OUTPUT [9,"nine","key":[],"key2":{"subkey":3.333}]
There are a number of ways this could be tightened up (and I'm sure there are some bugs, too), but you get the idea.
1 Comment
I have created the whole implementation of the JSON.stringify() method in a recursive way. Here is the link: https://javascript.plainenglish.io/create-your-own-implementation-of-json-stringify-simiplied-version-8ab6746cdd1
Github link: https://github.com/siddharth-sunchu/native-methods/blob/master/JSONStringfy.js
const JSONStringify = (obj) => {
const isArray = (value) => {
return Array.isArray(value) && typeof value === 'object';
};
const isObject = (value) => {
return typeof value === 'object' && value !== null && !Array.isArray(value);
};
const isString = (value) => {
return typeof value === 'string';
};
const isBoolean = (value) => {
return typeof value === 'boolean';
};
const isNumber = (value) => {
return typeof value === 'number';
};
const isNull = (value) => {
return value === null && typeof value === 'object';
};
const isNotNumber = (value) => {
return typeof value === 'number' && isNaN(value);
};
const isInfinity = (value) => {
return typeof value === 'number' && !isFinite(value);
};
const isDate = (value) => {
return typeof value === 'object' && value !== null && typeof value.getMonth === 'function';
};
const isUndefined = (value) => {
return value === undefined && typeof value === 'undefined';
};
const isFunction = (value) => {
return typeof value === 'function';
};
const isSymbol = (value) => {
return typeof value === 'symbol';
};
const restOfDataTypes = (value) => {
return isNumber(value) || isString(value) || isBoolean(value);
};
const ignoreDataTypes = (value) => {
return isUndefined(value) || isFunction(value) || isSymbol(value);
};
const nullDataTypes = (value) => {
return isNotNumber(value) || isInfinity(value) || isNull(value);
}
const arrayValuesNullTypes = (value) => {
return isNotNumber(value) || isInfinity(value) || isNull(value) || ignoreDataTypes(value);
}
const removeComma = (str) => {
const tempArr = str.split('');
tempArr.pop();
return tempArr.join('');
};
if (ignoreDataTypes(obj)) {
return undefined;
}
if (isDate(obj)) {
return `"${obj.toISOString()}"`;
}
if(nullDataTypes(obj)) {
return `${null}`
}
if(isSymbol(obj)) {
return undefined;
}
if (restOfDataTypes(obj)) {
const passQuotes = isString(obj) ? `"` : '';
return `${passQuotes}${obj}${passQuotes}`;
}
if (isArray(obj)) {
let arrStr = '';
obj.forEach((eachValue) => {
arrStr += arrayValuesNullTypes(eachValue) ? JSONStringify(null) : JSONStringify(eachValue);
arrStr += ','
});
return `[` + removeComma(arrStr) + `]`;
}
if (isObject(obj)) {
let objStr = '';
const objKeys = Object.keys(obj);
objKeys.forEach((eachKey) => {
const eachValue = obj[eachKey];
objStr += (!ignoreDataTypes(eachValue)) ? `"${eachKey}":${JSONStringify(eachValue)},` : '';
});
return `{` + removeComma(objStr) + `}`;
}
};
delete. Perhaps what you are missing is for...in to iterate over the properties of an object. (note: read the docs carefully)for..inloop, just pass the index of the next item as an argument in your recursive call.