Quick & dirty line-by-line diff function for JSON records

json_diff.js

// References:
// https://en.wikipedia.org/wiki/Longest_common_subsequence#Code_for_the_dynamic_programming_solution
// https://rajrajhans.com/2020/11/a-closer-look-at-diff-algorithms/
// https://www.npmjs.com/package/json-keys-sort?activeTab=code

function diff(a, b) {
    let s1 = JSON.stringify(json_sort(JSON.parse(a)), null, 4).split('\n');
    let s2 = JSON.stringify(json_sort(JSON.parse(b)), null, 4).split('\n');
    let m = s1.length, n = s2.length;
    let dp = new Array();
    for (let i=0; i<=m; i++) {
        dp.push(new Array(n+1).fill(-1));
    }
    let lcs_len = lcslen_dp(s1, s2, m, n, dp);
    let lcs_str = lcs_from_dp(s2, m, n, dp);
    // console.log('done');
    // console.log(lcs_str);
    
    let i=0, j=0, k=0, s;
    while (k < lcs_str.length) {
        s = lcs_str[k++];
        while (s1[i] != s && i < s1.length) {
            console.log('- ' + s1[i]);
            i++;
        }
        while (s2[j] != s && j < s2.length) {
            console.log('+ ' + s2[j]);
            j++;
        }
        console.log('  ' + s);
        i++;
        j++;
    }
    while (s1[i] != s && i < s1.length) console.log('- ' + s1[i++]);
    while (s2[j] != s && j < s2.length) console.log('+ ' + s2[j++]);
}


function lcslen_dp(s1, s2, i, j, dp) {
    if (i==0 || j==0) {
        dp[i][j] = 0;
        return 0;
    }
    else if (dp[i][j] != -1) {
        return dp[i][j];
    }
    let res;
    if (s1[i-1] == s2[j-1]) {
        res = 1 + lcslen_dp(s1, s2, i-1, j-1, dp);
    }
    else {
        res = Math.max(lcslen_dp(s1, s2, i-1, j, dp), lcslen_dp(s1, s2, i, j-1, dp));
    }
    dp[i][j] = res;
    return res;
}

function lcs_from_dp(s2, m, n, dp) {
    let lcs = [];
    for (let i=m,j=n; j>0; j--) {
        if (dp[i][j] == dp[i][j-1]) {
            continue;
        }
        else {
            lcs.unshift(s2[j-1]);
            i--;
        }
    }
    return lcs;
}

function t(d) {
    const c = 'constructor';
    const oc = {}[c];
    const ac = [][c];
    if (d && d !== null) return d[c] === oc ? 2 : d[c] === ac ? 1 : 0;
    return 0;
}

function json_sort(d) {
    if (t(d) == 1) {
        let n = [];
        for (let w = 0; w < d.length; w++) {
            let e = d[w];
            if (t(e) === 2 || t(e) === 1) n.push(json_sort(d));
            else n.push(e);
        }
        return n
    } else if (t(d) == 2) {
        let nk = [], k, n = {};
        k = Object.keys(d).sort((a,b)=>{if (a.length==b.length) return a < b ? -1 : a != b; else return a.length-b.length;});
        for (let j = 0; j < k.length; j++) {
            let key = k[j];
            if (t(d[key]) === 2) n[key] = json_sort(d[key]);
            else if (t(d[key]) === 1) {
                n[key] = [];
                for (let k = 0; k < d[key].length; k++) {
                    let e = d[key][k];
                    if (t(e) === 2 || t(e) === 1) n[key].push(json_sort(d[key][k]));
                    else n[key].push(d[key][k]);
                }
            } else n[key] = d[key];
        }
        return n;
    }
    else throw new Error("not an object or array");
}

let a = '{"glossary":{"title":"example glossary","GlossDiv":{"title":"S","GlossList":{"GlossEntry":{"ID":"SGML","SortAs":"SGML","GlossTerm":"Standard Generalized Markup Language","Acronym":"SGML","Abbrev":"ISO 8879:1986","GlossDef":{"para":"A meta-markup language, used to create markup languages such as DocBook.","GlossSeeAlso":["GML","XML"]},"GlossSee":"markup"}}}}}';
let b = '{"glossary":{"title":"test glossary","GlossDiv":{"title":"S","GlossList":{"GlossEntry":{"ID":"SGML","GlossTerm":"Standard Generalized Markup Language","Acronym":"SGML","Abbrev":"ISO 8879:1986","GlossDef":{"para":"A meta-markup language, used to create markup languages such as DocBook.","GlossSeeAlso":["GML","XHTML","XML"]},"GlossSee":"markup"}}}}}';

diff(a, b);