Using JavaScript, given a JSON value, recursively find all JSON objects, then sort keys in-place

Question

Some background: JavaScript is not my primary language, so I'm looking to get some constructive criticism here.

I built a tiny single page HTML app that pretty prints JSON text. It's very useful when I am looking a process logs that dump JSON without pretty printing.

In my tool, I added a checkbox to optionally sort the keys for all JSON objects.

To be clear, I am only targetting the most modern browsers, so please assume the latest and greatest of JavaScript is available.

function _sort_keys_deeply(json_thing)
{
    if (false === _is_sortable(json_thing))
    {
        return json_thing;
    }
    if (Array.isArray(json_thing))
    {
        for (var i = 0; i < json_thing.length; ++i)
        {
            const val = json_thing[i];
            if (_is_sortable(val))
            {
                const val2 = _sort_keys_deeply(val);
                json_thing[i] = val2;
            }
        }
        return json_thing;
    }
    // else: object
    const sorted_obj = _sort_object_keys(json_thing);
    const key_arr = Object.keys(sorted_obj);
    for (var i = 0; i < key_arr.length; ++i)
    {
        const key = key_arr[i];
        const val = sorted_obj[key];
        if (_is_sortable(val))
        {
            const val2 = _sort_keys_deeply(val);
            sorted_obj[key] = val2;
        }
    }
    return sorted_obj;
}
function _is_sortable(z)
{
    // Beware: null is type object, but is not sortable.
    const x = (null !== z) && ('object' === typeof(z) || Array.isArray(z));
    return x;
}
// Ref: https://stackoverflow.com/a/31102605/257299
function _sort_object_keys(obj)
{
    const key_arr = Object.keys(obj);
    // In-place array sort
    key_arr.sort();
    // Ref: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce
    const f =
        function(new_obj2, key/*, index, array*/)
        {
            new_obj2[key] = obj[key];
            return new_obj2;
        };
    const new_obj = {};
    key_arr.reduce(f, new_obj);
    return new_obj;
}

Answer 1

This code was well-commented and easy enough to figure out. Well done on that front.

Stylistic notes:

• In JS it's idiomatic to use camelCase, not snake_case.
• This code is formatted like C# code. In JS, open brace on same line is more common.
• Feel free to leave out the semi-colons.

Design notes:

• You can make the small helper functions one-liners and define them within the main function. This way, conceptually, you'll be writing a single function to solve a single problem.
• In my rewrite below, I've left off the braces on the single-statement ifs. That's a personal preference but makes some people uneasy. Feel free to add them back.

Here is my attempt at a rewrite based on these notes. Let me know if I've unwittingly changed any behavior:

function sorted(o) {
  const isObj = x => typeof(x) === 'object'
  const isArr = Array.isArray

  // Beware: null is type object, but is not sortable.
  const isSortable = x => (x !== null) && (isObj(x) || isArr(x))

  if (!isSortable(o))
    return o

  if (isArr(o))
    return o.map(sorted)

  if (isObj(o))
    return Object.keys(o).sort().reduce(
      (m, x) => (m[x] = isSortable(o[x]) ? sorted(o[x]) : o[x], m),
      {}
    )
}

Try it online!

Answer 2

JSON

JSON is a not a thing, it is a transport file format, held in memory as a String In JavaScript it is parsed using JSON.parse and the result is an Object. To refer to an object as a json_thing is incorrect (yes its a "thing") but it's not a string or blob formatted to as JSON.

The only thing that makes an object unique when created from a JSON string is that you are guaranteed not to have cyclic references.

General notes.

There is a lot of code noise in your code. Code noise is anything that does not contribute to the algorithm process

You modify the array in place, but you copy objects. Best if you treat arrays and objects the same, either in place or as a copy. The rewrites give examples of both

Call stack overflow

JavaScript uses a call stack (as do most languages) unfortunately almost all JavaScript implementations do not recognize tail calls (even though its part of the ECMAScript6 standard) meaning that recursion is dangerous.

There is no way to know how deep the call stack is, nor how deep you must go to complete the task. Always be wary of this when creating recursive code.

The rewrites gives an example of a non recursive solution that can process a much deeper object than a recursive function can.

Code style

• Declare variable at top of function as this is where variables declared as var are created. Function declaration (eg function name(){}) are also hoisted to the top of their scope in JavaScript.

  Note that let and const are block scope {/*block*/} and are not hoisted to the top of their scope. You can not use them before they are declared.

• If you don't need the index use a for...of of loop rather than a for loop.

  Note Using callback iterators can add overhead to processing and are generals slower than for loops.

• Avoid single use variables unless they help keep the code clean.

• JavaScript logical operators always execute in the same order (unlike C/C++) and can thus be used to reduce code noise via short circuit syntax style. Eg if (foo) { foo = 0 } can be foo && (foo = 0);

  Note that the () around the second (3rd etc...) logical clause is required if there is an assignment operator within a short circuit expression.

  Note you can not short circuit flow control eg foo && return is illegal. Same for break, continue, if, for etc...

  As the order of logical and grouped expressions / statements is always the same you can optimize them using most likely outcome. eg testing z !== null && typeof z === "object" can be optimized as typeof z === "object" && z !== null as it is far more likely that z is not an object than it being null

• Use the short form/style when you can. Eg if (false === isSortable(obj)) { can be if (!isSortable(obj)) {

• Function arguments are function scoped and writeable (almost identical to var). Reuse them if it helps reduce code noise.

• Object.keys, Object.entries Object.values works on Array, Object, and String thus you do not need to treat object and array separately.

• Array is a typeof "object". The Array.isArray in isSortable is redundant.

  Note that typeof is a JavaScript operator and not a function. typeof(z) is the same as typeof z the grouping operator has no effect in this case

• You can use Object.fromEntries to create an object from an array of key, name pairs. Object.fromEntries([["A", 1], ["B", 2]]) will define an object {A:1, B:1}

Rewrite

Rewrite removes the code noise and redundant code.

I have provided three versions.

1. uses recursion and creates a copy of objects that are sorted. This rewrite is the only one the matches you function`s behavior

2. uses a stack and sorts object keys in place. Only arrays and object are pushed to the stack.

3. Same as 2 but checks for cyclic references and as such is the only rewrite safe to use.

NOTE ONLY use the first two on objects that do not have cyclic references. The recursive example will throw an error very quickly, the second will need to use up memory before it has a problem (this will lock the page as it chews up memory), and then depending on the engine could crash the page/thread or throw an error.

Recursive

function sortKeysDeeply(obj) {
    if (isObj(obj)) {
        !Array.isArray(obj) && (obj = sortObjectKeys(obj));
        for (const [key, val] of Object.entries(sorted)) {
            isObj(val) && (obj[key] = sortKeysDeeply(val));
        }
    }
    return obj;
}

Using a stack

function sortKeysDeeply(obj) {
    const stack = [];
    if (isObj(obj)) {
        stack.push(obj);
        while (stack.length) {
            let o = stack.pop();
            o = !Array.isArray(o) && sortInPlaceObjectKeys(o);
            for (const val of Object.values(o)) { isObj(val) && stack.push(val) }
        }
    }
    return obj;
}

Cyclic safe stack

This uses a WeakSet to track which object references have been encountered.

A week set only holds the generated hash rather than the object and thus uses a little less memory than Set and reduces the GC workload.

You can use this in the recursive code as well.

function sortKeysDeeply(obj) {
    const stack = [], checked = new WeakSet();
    if (isObj(obj)) {
        stack.push(obj);
        while (stack.length) {
            let o = stack.pop();
            checked.add(o);
            o = !Array.isArray(o) && sortInPlaceObjectKeys(o);
            for (const val of Object.values(o)) { 
                isObj(val) && !checked.has(val) && stack.push(val);
            }
        }
    }
    return obj;
}

Helper functions

Function required by above rewrites.

const strSorter = (a, b) => a > b ? 1 : a < b ? -1 : 0;
const isObj = obj => 'object' === typeof(obj) && null !== obj;
const sortObjectKeys = obj => 
    Object.fromEntries(Object.entries(obj).sort((a, b) => strSorter(a[0], b[0])));
        
const sortInPlaceObjectKeys = obj => {
    const sorted = Object.entries(obj).sort((a, b) => strSorter(a[0], b[0]));
    for (const [key] of sorted) { delete obj[key] }
    return Object.assign(obj, Object.fromEntries(sorted));
}