Javascript atravesar árbol JSON

El problema

Tenemos el árbol de menú de una aplicación. Cada hoja tiene unos permisos asociados. Sólo queremos mostrar los nodos de los que el usuario tenga algún permiso.

Una posible forma de hacerlo es recorrer el árbol una vez y acumular en los nodos los permisos del nivel por debajo. El recorrido sería en postorden.

Los usuarios tienen grupos de permisos (roles). En el momento de generar el menú de un usuario particular, deberemos volver a recorrer el árbol, esta vez en anchura (por niveles), tomando sólo aquellos nodos que tengan algún permiso coincidente. Si no hay ninguno, no es necesario bajar al siguiente nivel de esa rama.

Árbol de menús

var modulos = [


    {permiso: [], descripcion: 'Almacenes', url: '#',
        submenus: [
            {permiso: ['compras.alb.ver'], descripcion: 'Artículos',   url: '/app/articulos'},
            {permiso: ['compras.prov.ver'], descripcion: 'Proveedores', url: '/app/proveedores'},
            {permiso: ['alm.inv.ver'], descripcion: 'Inventario',  url: '/app/inventario'},
            {permiso: ['alm.edit'], descripcion: 'Almacenes',   url: '/app/almacenes'}
        ]
    },

    {permiso: [], descripcion: 'Compras', url: '#',
        submenus: [
            {permiso: ['compras.pedidos.ver'], descripcion: 'Pedidos', url: '/app/compras/pedidos'},
            {permiso: ['compras.albaranes.ver'], descripcion: 'Albaranes', url: '/app/compras/albaranes', 
            submenus: [
             {permiso: ['compras.alb.edt'], descripcion: 'Editar',   url: '/app/albaranes/edit'},
            {permiso: ['compras.alb.lst'], descripcion: 'Listar', url: '/app/albaranes/list'},
            ]},
        ]
    },
];

El nodo Almacenes debería contener los permisos de los que tiene por debajo, el nodo Albaranes debería contener [compras.alb.edt, compras.alb.lst] y el nodo Compras [compras.pedidos.ver, compras.albaranes.ver, compras.alb.edt, compras.alb.lst].

Recorrido de un árbol JSON en postorden

Observamos que tenemos tanto objects como arrays: Atravesamos los arrays con forEach y los objetos examinando sus claves con for (var key in obj) . Bajamos hasta la primera hoja de la izquierda, visitando las hermanas para subir después al nodo superior. El proceso se repite de forma recursiva hasta haber visitado todos los nodos. Mantenemos la referencia al nodo inmediatamente superior con parent para poder acumular en él los permisos.

var _und = require("underscore");

// último nodo visitado
var lastObject=null;

/** 
* Atraviesa un arbol JSON en postorden
* @param x - el nodo actual
* @param level - sólo para debug, caracter para imprimir delante de los nodos
* @parent - referencia al nodo padre o null
*/
function traverse(x, level, parent) {
    if (isArray(x)) {
        traverseArray(x, level, parent);
    } else if ((typeof x === 'object') && (x !== null)) {
        traverseObject(x, level, parent);
    } else {
        // tipus primitiu
    }
}

/**
* Determina si el tipo es array
* @param o - el objeto javascript
* @return true si es un aray
*/
function isArray(o) {
    return Object.prototype.toString.call(o) === '[object Array]';
}

function traverseArray(arr, level, parent) {
    arr.forEach(function(x) {
        traverse(x, level + "  ", parent);
    });
    //console.log(level + "<array>");
}

function traverseObject(obj, level, parent) {
    //console.log(level + "<object>");

    for (var key in obj) {
        if (obj.hasOwnProperty(key)) {
            lastObj=parent
            traverse(obj[key], level + "    ", obj);
        }
    }

    // Acumulamos los permisos en el padre
    // usamos _und.union para evitar permisos duplicados
    if (obj && obj.descripcion) {
        var p=''
        if (parent) {
            p=parent.descripcion           
            parent.permiso=_und.union(parent.permiso, obj.permiso)
        } else {
            p='/'
        }
        console.log('visitant', obj.descripcion,'amb pare', p);
    }
}

Ahora ya sólo queda hacer

traverse(modulos, '')

Para mostrar los menús, podemos poner una marca de visibilidad y enviar el árbol al renderizador de plantillas que sólo mostrará los que tengan visible==true.

var recurseMenus= function(permisos, m) {
    _und.each(m, function(md) {
        //logger.debug('mirant si menu', md.descripcion, 'te el permís', md.permiso)
        // hacemos la intersección del conjunto de permisos del usuario con los del nodo actual
        var interseccio=_und.intersection(md.permiso, permisos)
        // si el resultado de la intersección es diferente del conjunto vacío el usuario puede ver este menú
        if (_und.size(interseccio)>0) {
            //logger.debug('te permis de ', md.permiso)
            md.visible=true
            if (md.submenus) {
                recurseMenus(permisos, md.submenus)
            }
        } else {
            //logger.debug('no te el permis')
            md.visible = false;
        }
    })
}

Referencias

https://www.quora.com/How-do-you-loop-through-a-complex-JSON-tree-of-objects-and-arrays-in-JavaScript