Collapse JOIN query result sets into a hierarchical object graph

collapse.js

'use strict';

if (!String.prototype.endsWith) {
    String.prototype.endsWith = function(searchStr, Position) {
        // This works much better than >= because
        // it compensates for NaN:
        if (!(Position < this.length))
            Position = this.length;
        else
            Position |= 0; // round position
        return this.substr(Position - searchStr.length,
                searchStr.length) === searchStr;
    };
}

if (!String.prototype.startsWith) {
    String.prototype.startsWith = function(searchString, position) {
        position = position || 0;
        return this.indexOf(searchString, position) === position;
    };
}

/**
 * Collapses tabular result sets into a (hierarchical) object graph based on
 * column nomenclature. Given a query that selects parent and child columns as
 * this.id, this.val, this.children.id, this.children.val, this will return an
 * array of objects in the form
 *
 * {id: 1, val: 'parent val', children: [{id: 11, val: 'child val'}]}
 *
 * and so on.
 *
 * @param  {[type]} data    Data to operate on.
 * @return {[type]}         Transformed object graph.
 */
module.exports = function (data) {

    var parent = 'this';
    var pk = 'id';
    var options = {};

    if (!data || data.length === 0) {
        return [];
    }

    // console.log(data);

    /* schemata defines the structural relationships of the entity-models and the fields each model consists of, and maps
     * the final field names to the original columns in the query resultset.
     * example: {id: parent__id, name: parent__name, children: {id: children__id, name: children__name}} */

    var schemata = Object.keys(data[0]).reduce(function (acc, c) {
        var tuple = c.split('.');
        var entity = acc;
        var name;

        do {
            name = tuple.shift();
            if (name !== parent) {

                // avoid creating a parent schema, we want that to be the root
                // this almost certainly does Bad things if the graph is cyclic
                // but fortunately we don't need to worry about that since the
                // column name format can't define a backwards relationship

                if (!entity.hasOwnProperty(name)) {
                    entity[name] = {};
                }
                entity = entity[name];
            }
        } while (tuple.length > 1);	// walk as deep as we need to for child__grandchild__greatgrandchild__fieldname etc
        entity[tuple.pop()] = c;	// set {fieldname: path__to__fieldname} pair

        return acc;
    }, {});

    /* mapping is a nested dictionary of id:entity but otherwise in the form of the final structure we're trying to build,
     * effectively hashing ids to ensure we don't duplicate any entities in cases where multiple dependent tables are
     * joined into the source query.
     *
     * example: {1: {id: 1, name: 'hi', children: {111: {id: 111, name: 'ih'}}} */
    var mapping = data.reduce(function (acc, row) {
        return (function build (obj, schema, parents, name) {

            var opts = options[name] || {};
            //var pkField = 'this.' + name + '.' + (opts.pk || pk);
            var pkField = name + '.' + (opts.pk || pk);

            if (parents.length) {
                pkField = parents.join('.') + '.' + pkField;
                // anything deeper than child.id needs to build the full column name
            }

            if (!pkField.startsWith(parent)) { pkField = parent + '.' + pkField; }

            var id = row[pkField];

            if (id === null) {						// null id means this entity doesn't exist and was likely outer joined in
                return;
            } else if (!obj.hasOwnProperty(id)) {	// this entity is new
                obj[id] = {};
            }

            Object.keys(schema).forEach(function (c) {

                if (typeof schema[c] === 'string') {	// c is a field
                    obj[id][c] = row[schema[c]];
                } else {								// c is a relation
                    if (!obj[id].hasOwnProperty(c)) {
                        obj[id][c] = {};				// current object does not have relation defined, initialize it
                    }

                    // if parent isn't the root schema include that when we recurse, otherwise ignore
                    build(obj[id][c], schema[c], (name !== parent) ? parents.concat([name]): parents, c);
                }

            });

            return obj;
        })(acc, schemata, [], parent);
    }, {});

    /* Build the final graph. The structure and data already exists in mapping, but we need to transform the {id: entity} structures
     * into arrays of entities (or flat objects if required).
     *
     * example: [{id: 1, name: 'hi', children: [{id: 111, name: 'ih'}]}] */
    return (function transform(schema, map, accumulator) {
        // for every id:entity pair in the current level of mapping, if the schema defines any dependent
        // entities recurse and transform them, then push the current object into the accumulator and return
        // console.log('map', map);
        // console.log('accumulator', accumulator);

        return Object.keys(map).reduce(function (acc, k) {

            Object.keys(schema)
                .filter(function (c) { return typeof schema[c] === 'object'; })	// just structure now
                .forEach(function (c) {

                    // we have to init & pass the accumulator into the *next* recursion since the single
                    // option is defined on the child rather than the parent
                    // a property name ending with [] is a array otherwise is a object

                    var isArray = c.endsWith('[]');

                    if (isArray) {

                        map[k][c.replace('[]', '')] = transform(schema[c], map[k][c], []);
                        if (map[k][c]) {
                            // delete original key named with []
                            // for example: delete key named "labels[]"
                            delete map[k][c];
                        }

                    } else {
                        var value = transform(schema[c], map[k][c], {});
                        map[k][c] = Array.isArray(value) ? null : value;
                    }

                    // if (options[c] && options[c].sort) {
                    //     var sort = options[c].sort;
                    //     map[k][c].sort(function (a, b) {
                    //         if (a[sort] > b[sort]) { return 1; }
                    //         else if (a[sort] < b[sort]) { return -1; }
                    //         return 0;
                    //     });
                    // }
                });

            if (Array.isArray(accumulator)) {
                acc.push(map[k]);
            }
            else {
                acc = map[k];
            }

            return acc;

        }, []);

    })(schemata, mapping, []);
};

tests.js

'use strict';

var assert = require('chai').assert;
var collapse = require('./index');

describe('lib/collapse', function () {

    describe('lib/collapse original tests cases', function() {

        it('should return empty if given empty', function () {
            assert.deepEqual([], collapse([]));
        });

        it('should collapse simple tree structures', function () {
            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 11, 'this.children[].val': 'c1'},
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 12, 'this.children[].val': 'c2'}
            ];
            var result = collapse(rows);
            var expectedResult = [{id: 1, val: 'p1', children: [{id: 11, val: 'c1'}, {id: 12, val: 'c2'}]}];
            assert.deepEqual(result, expectedResult);
        });

        it('should sort children if an option is specified', function () {
            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 11, 'this.children[].val': 'c2'},
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 12, 'this.children[].val': 'c1'}
            ];

            var result = collapse(rows);
            var expectedResult = [{id: 1, val: 'p1', children: [{id: 11, val: 'c2'}, {id: 12, val: 'c1'}]}];
            assert.deepEqual(result, expectedResult);
        });


        it('should collapse multiple children with the same parent', function () {

            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.children1[].id': 11, 'this.children1[].val': 'c1', 'this.children2[].id': 21, 'this.children2[].val': 'd1'},
                {'this.id': 1, 'this.val': 'p1', 'this.children1[].id': 12, 'this.children1[].val': 'c2', 'this.children2[].id': 22, 'this.children2[].val': 'd2'},
                {'this.id': 1, 'this.val': 'p1', 'this.children1[].id': 12, 'this.children1[].val': 'c2', 'this.children2[].id': 23, 'this.children2[].val': 'd3'}
            ];

            var result = collapse(rows);
            var expectedResult = [{
                id: 1,
                val: 'p1',
                children1: [{id: 11, val: 'c1'}, {id: 12, val: 'c2'}],
                children2: [{id: 21, val: 'd1'}, {id: 22, val: 'd2'}, {id: 23, val: 'd3'}]
            }];

            assert.deepEqual(result, expectedResult);
        });

        it('should collapse children into other children', function () {

            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.children1[].id': 11, 'this.children1[].val': 'c1', 'this.children1[].children2[].id': 21, 'this.children1[].children2[].val': 'd1'},
                {'this.id': 1, 'this.val': 'p1', 'this.children1[].id': 12, 'this.children1[].val': 'c2', 'this.children1[].children2[].id': 22, 'this.children1[].children2[].val': 'd2'},
                {'this.id': 1, 'this.val': 'p1', 'this.children1[].id': 12, 'this.children1[].val': 'c2', 'this.children1[].children2[].id': 23, 'this.children1[].children2[].val': 'd3'}
            ];

            var result = collapse(rows);
            var expectedResult = [{
                id: 1,
                val: 'p1',
                children1: [{
                    id: 11,
                    val: 'c1',
                    children2: [{id: 21, val: 'd1'}]
                }, {
                    id: 12,
                    val: 'c2',
                    children2: [{id: 22, val: 'd2'}, {id: 23, val: 'd3'}]
                }]
            }];
            assert.deepEqual(result, expectedResult);
        });


        it('should create empty child arrays if given null children from outer joins', function () {
            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': null, 'this.children[].val': null},
                {'this.id': 2, 'this.val': 'p2', 'this.children[].id': 11, 'this.children[].val': 'c1'}
            ];

            var result = collapse(rows);
            var expetedResult = [{id: 1, val: 'p1', children: []}, {id: 2, val: 'p2', children: [{id: 11, val: 'c1'}]}];
            assert.deepEqual(result, expetedResult);
        });


        it('should collapse 1:1 relations', function () {
            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.child.id': 11, 'this.child.val': 'c1'}
            ];

            var result = collapse(rows);
            var expectedResult = [{id: 1, val: 'p1', child: {id: 11, val: 'c1'}}];
            assert.deepEqual(result, expectedResult);
        });

        it('should collapse 1:1 relations with null value', function () {
            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.child.id': 11, 'this.child.val': 'c1'},
                {'this.id': 2, 'this.val': 'p2', 'this.child.id': null, 'this.child.val': null},
                {'this.id': 3, 'this.val': 'p3', 'this.child.id': 12, 'this.child.val': 'c2'}
            ];

            var result = collapse(rows);
            var expectedResult = [
                {id: 1, val: 'p1', child: {id: 11, val: 'c1'}},
                {id: 2, val: 'p2', child: null},
                {id: 3, val: 'p3', child: {id: 12, val: 'c2'}}
            ];
            assert.deepEqual(result, expectedResult);
        });

        it('should collapse with duplicated rows', function () {

            // this dataset is 'bad' in that you're not usually going to see 100% duplicate rows unless you've really screwed up
            // but it's more legible than reproducing the 'multiple children' data and tests the deduplication just the same
            var rows = [
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 11, 'this.children[].val': 'c1'},
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 12, 'this.children[].val': 'c2'}, /* <---- duplicated row */
                {'this.id': 1, 'this.val': 'p1', 'this.children[].id': 12, 'this.children[].val': 'c2'}  /* <---- duplicated row */
            ];

            var result = collapse(rows);
            var expectedResult = [{id: 1, val: 'p1', children: [{id: 11, val: 'c1'}, {id: 12, val: 'c2'}]}];
            assert.deepEqual(result, expectedResult);
        });

        it('should apply new parents only in the correct scope', function() {

            var rows = [

                {
                    'this.id': 1,
                    'this.account.id': 1,
                    'this.name': 'Eduardo Luiz',
                    'this.contact.email': 'email',
                    'this.contact.phone': 'phone',
                    'this.notes': null,
                    'this.archived': false,
                    'this.address.zipCode': 'zip',
                    'this.address.street': 'street',
                    'this.address.number': 'number',
                    'this.address.complement': null,
                    'this.address.neighborhood': null,
                    'this.address.city': 'Sao Paulo',
                    'this.address.state': 'Sao Paulo',
                    'this.address.coords.latitude': '1',
                    'this.address.coords.longitude': '2',
                    'this.labels[].id': '297726d0-301d-4de6-b9a4-e439b81f44ba',
                    'this.labels[].name': 'Contrato',
                    'this.labels[].color': 'yellow',
                    'this.labels[].type': 1
                },
                {
                    'this.id': 1,
                    'this.account.id': 1,
                    'this.name': 'Eduardo Luiz',
                    'this.contact.email': 'email',
                    'this.contact.phone': 'phone',
                    'this.notes': null,
                    'this.archived': false,
                    'this.address.zipCode': 'zip',
                    'this.address.street': 'street',
                    'this.address.number': 'number',
                    'this.address.complement': null,
                    'this.address.neighborhood': null,
                    'this.address.city': 'Sao Paulo',
                    'this.address.state': 'Sao Paulo',
                    'this.address.coords.latitude': '1',
                    'this.address.coords.longitude': '2',
                    'this.labels[].id': '1db6e07f-91e2-42fb-b65c-9a364b6bad4c',
                    'this.labels[].name': 'Particular',
                    'this.labels[].color': 'purple',
                    'this.labels[].type': 1
                }
            ];

            var result = collapse(rows);
            var expectedResult = [{
                'id': 1,
                'account': {
                    'id': 1
                },
                'name': 'Eduardo Luiz',
                'contact': {
                    'email': 'email',
                    'phone': 'phone'
                },
                'notes': null,
                'archived': false,
                'address': {
                    'zipCode': 'zip',
                    'street': 'street',
                    'number': 'number',
                    'complement': null,
                    'neighborhood': null,
                    'city': 'Sao Paulo',
                    'state': 'Sao Paulo',
                    'coords': {
                        'latitude': '1',
                        'longitude': '2'
                    }
                },
                'labels': [
                    {
                        'id': '297726d0-301d-4de6-b9a4-e439b81f44ba',
                        'name': 'Contrato',
                        'color': 'yellow',
                        'type': 1
                    }, {
                        'id': '1db6e07f-91e2-42fb-b65c-9a364b6bad4c',
                        'name': 'Particular',
                        'color': 'purple',
                        'type': 1
                    }
                ]
            }];
            assert.deepEqual(result, expectedResult);
        });

    });

    describe('real life scenarios', function() {

        it('should collapse two tasks', function () {
            var rows = [
                {'this.id': 1, 'this.todo': 'do task 1'},
                {'this.id': 2, 'this.todo': 'do task 2'}
            ];

            var result = collapse(rows);
            var expectedResult = [
                {id: 1, todo: 'do task 1'},
                {id: 2, todo: 'do task 2'}
            ];
            assert.deepEqual(result, expectedResult);
        });

        it('should collapse two tasks with simple customers', function () {

            var rows = [
                {'this.id': 1, 'this.todo': 'do task 1', 'this.customer.id': 3, 'this.customer.name': 'Luiz'},
                {'this.id': 2, 'this.todo': 'do task 2', 'this.customer.id': 4, 'this.customer.name': 'Felipe'}
            ];

            var result = collapse(rows);
            var expectedResult = [
                {id: 1, todo: 'do task 1', customer: {id: 3, name: 'Luiz'}},
                {id: 2, todo: 'do task 2', customer: {id: 4, name: 'Felipe'}}
            ];
            assert.deepEqual(result, expectedResult);
        });

        it('should collapse two tasks with customers and its address', function () {

            var rows = [
                {'this.id': 1, 'this.todo': 'do task 1', 'this.customer.id': 3, 'this.customer.name': 'Luiz', 'this.customer.address.street': 'Rua dos Pinheiros 383', 'this.customer.address.coords.latitude': -1, 'this.customer.address.coords.longitude': -2 },
                {'this.id': 2, 'this.todo': 'do task 2', 'this.customer.id': 4, 'this.customer.name': 'Felipe', 'this.customer.address.street': 'Avenida Rebouças 130', 'this.customer.address.coords.latitude': -3, 'this.customer.address.coords.longitude': -5 }
            ];

            var result = collapse(rows);
            var expectedResult = [
                {id: 1, todo: 'do task 1', customer: {id: 3, name: 'Luiz', address: { street: 'Rua dos Pinheiros 383', coords: { latitude: -1, longitude: -2 }}}},
                {id: 2, todo: 'do task 2', customer: {id: 4, name: 'Felipe', address: { street: 'Avenida Rebouças 130', coords: { latitude: -3, longitude: -5 }}}}
            ];
            assert.deepEqual(result, expectedResult);
        });

        it('should collapse a complete customer with address and labels', function() {

            var rows = [
                {
                    "this.id": 1,
                    "this.name": "Eduardo Luiz",
                    "this.account.id": 1,
                    "this.contact.email": "eduardoluizsantos@gmail.com",
                    "this.contact.phone": "11965874523",
                    "this.notes": null,
                    "this.archived": false,
                    "this.address.zipCode": "05422010",
                    "this.address.street": "Rua dos Pinheiros",
                    "this.address.number": "383",
                    "this.address.complement": null,
                    "this.address.neighborhood": null,
                    "this.address.city": "Sao Paulo",
                    "this.address.state": "Sao Paulo",
                    "this.address.coords.latitude": "1",
                    "this.address.coords.longitude": "2",
                    "this.labels[].id": "297726d0-301d-4de6-b9a4-e439b81f44ba",
                    "this.labels[].name": "Contrato",
                    "this.labels[].color": "yellow",
                    "this.labels[].type": 1
                },
                {
                    "this.id": 1,
                    "this.account.id": 1,
                    "this.name": "Eduardo Luiz",
                    "this.contact.email": "eduardoluizsantos@gmail.com",
                    "this.contact.phone": "11965874523",
                    "this.notes": null,
                    "this.archived": false,
                    "this.address.zipCode": "05422010",
                    "this.address.street": "Rua dos Pinheiros",
                    "this.address.number": "383",
                    "this.address.complement": null,
                    "this.address.neighborhood": null,
                    "this.address.city": "Sao Paulo",
                    "this.address.state": "Sao Paulo",
                    "this.address.coords.latitude": "1",
                    "this.address.coords.longitude": "2",
                    "this.labels[].id": "1db6e07f-91e2-42fb-b65c-9a364b6bad4c",
                    "this.labels[].name": "Particular",
                    "this.labels[].color": "purple",
                    "this.labels[].type": 1
                }
            ];

            var result = collapse(rows);
            var expectedResult = [
                {
                    "id": 1,
                    "account": {
                        "id": 1
                    },
                    "name": "Eduardo Luiz",
                    "contact": {
                        "email": "eduardoluizsantos@gmail.com",
                        "phone": "11965874523"
                    },
                    "notes": null,
                    "archived": false,
                    "address": {
                        "zipCode": "05422010",
                        "street": "Rua dos Pinheiros",
                        "number": "383",
                        "complement": null,
                        "neighborhood": null,
                        "city": "Sao Paulo",
                        "state": "Sao Paulo",
                        "coords": {
                            "latitude": "1",
                            "longitude": "2"
                        }
                    },
                    "labels": [
                        {
                            "id": "297726d0-301d-4de6-b9a4-e439b81f44ba",
                            "name": "Contrato",
                            "color": "yellow",
                            "type": 1
                        },
                        {
                            "id": "1db6e07f-91e2-42fb-b65c-9a364b6bad4c",
                            "name": "Particular",
                            "color": "purple",
                            "type": 1
                        }
                    ]
                }
            ];
            assert.deepEqual(result, expectedResult);
        });

        it('should collapse a complete form with questions and options', function(){
            var rows = [
                {
                    "this.id": "528ad1ca-c889-46f0-b044-689e0986dab2",
                    "this.name": "Formulário",
                    "this.questions[].id": "acf9af3f-f0ce-4ac9-93c2-c18e06d887ca",
                    "this.questions[].type": 6,
                    "this.questions[].title": "Qual alimento pode ser ser transformado em código?",
                    "this.questions[].required": false,
                    "this.questions[].position": 7,
                    "this.questions[].options[].id": "a",
                    "this.questions[].options[].value": "Carne Completo",
                    "this.questions[].options[].position": 1
                },
                {
                    "this.id": "528ad1ca-c889-46f0-b044-689e0986dab2",
                    "this.name": "Formulário",
                    "this.questions[].id": "acf9af3f-f0ce-4ac9-93c2-c18e06d887ca",
                    "this.questions[].type": 6,
                    "this.questions[].title": "Qual alimento pode ser ser transformado em código?",
                    "this.questions[].required": false,
                    "this.questions[].position": 7,
                    "this.questions[].options[].id": "b",
                    "this.questions[].options[].value": "Café",
                    "this.questions[].options[].position": 2
                }
            ];

            var result = collapse(rows);
            var expectedResult = [{
                "id": '528ad1ca-c889-46f0-b044-689e0986dab2',
                "name": 'Formulário',
                "questions": [{
                    "id": 'acf9af3f-f0ce-4ac9-93c2-c18e06d887ca',
                    "type": 6,
                    "title": 'Qual alimento pode ser ser transformado em código?',
                    "required": false,
                    "position": 7,
                    "options": [
                        {
                            "id": 'a',
                            "value": "Carne Completo",
                            "position": 1
                        },
                        {
                            "id": 'b',
                            "value": "Café",
                            "position": 2
                        }
                    ]
                }]
            }];

            assert.deepEqual(result, expectedResult);
        });

    });
});