Problem with cyclic values

[brettz9]

As per the w3c/IDBObjectStore.add.js test, recursive values ought to be supported, but the current Sca.js file apparently fails with this because it is using JSON.stringify.

Once implemented, that test should no longer be skipped as it is now to prevent subsequent test failures.

[axemclion]

@brettz9 We could use JSON Object Graph - I used it here - https://github.com/nparashuram/maya-kai/blob/master/src/util/jsog.js

[brettz9]

Sounds cool, @axemclion...

[brettz9]

Btw, @axemclion , any chance you might be inspired to adapt your JSOG to support arrays with self-referencing items as well as objects which can reference back to the root object?

In the decycle code currently in use in IndexedDBShim, there is this code comment:

    // The
    // duplicate references (which might be forming cycles) are replaced with
    // an object of the form
    //      {$ref: PATH}
    // So,
    //      var a = [];
    //      a[0] = a;
    //      return JSON.stringify(JSON.decycle(a));
    // produces the string '[{"$ref":"$"}]'.

(And if you are so inclined and wouldn't mind basing it off of the following which I've adapted to fit the stricter ESLint standards:)

const JSOG = {};

let nextId = 0;

const isArray = Array.isArray || function (obj) {
    return Object.prototype.toString.call(obj) === '[object Array]';
};

const hasCustomJsonificaiton = function (obj) {
    return obj.toJSON != null;
};

const JSOGObjectID = '__jsogObjectId';

JSOG.encode = function (original, idProperty, refProperty) {
    if (idProperty == null) {
        idProperty = '@id';
    }
    if (refProperty == null) {
        refProperty = '@ref';
    }
    const sofar = {};
    const objectsWithJSOGObjectID = [];

    const idOf = function (obj) {
        if (!obj[JSOGObjectID]) {
            obj[JSOGObjectID] = '' + (nextId++);
            objectsWithJSOGObjectID.push(obj);
        }
        return obj[JSOGObjectID];
    };
    const doEncode = function (original) {
        const encodeObject = function (original) {
            let key, obj1, obj2, value;
            const id = idOf(original);
            if (sofar[id]) {
                return ( // eslint-disable-line no-return-assign
                    obj1 = {},
                    obj1['' + refProperty] = id,
                    obj1
                );
            }
            const result = sofar[id] = (
                obj2 = {},
                obj2['' + idProperty] = id,
                obj2
            );
            for (key in original) {
                value = original[key];
                if (key !== JSOGObjectID) {
                    result[key] = doEncode(value);
                }
            }
            return result;
        };
        const encodeArray = function (original) {
            let val;
            return (function () {
                let i, len;
                const results = [];
                for (i = 0, len = original.length; i < len; i++) {
                    val = original[i];
                    results.push(doEncode(val));
                }
                return results;
            })();
        };
        if (original == null || hasCustomJsonificaiton(original)) {
            return original;
        }
        if (isArray(original)) {
            return encodeArray(original);
        }
        if (typeof original === 'object') {
            return encodeObject(original);
        }
        return original;
    };

    const result = doEncode(original);
    for (let i = 0; i < objectsWithJSOGObjectID.length; i++) {
        delete objectsWithJSOGObjectID[i][JSOGObjectID];
    }

    return result;
};

JSOG.decode = function (encoded, idProperty, refProperty) {
    if (idProperty == null) {
        idProperty = '@id';
    }
    if (refProperty == null) {
        refProperty = '@ref';
    }
    const found = {};
    const doDecode = function (encoded) {
        const decodeObject = function (encoded) {
            let id, key, ref, value;
            ref = encoded[refProperty];
            if (ref != null) {
                ref = ref.toString();
            }
            if (ref != null) {
                return found[ref];
            }
            const result = {};
            id = encoded[idProperty];
            if (id != null) {
                id = id.toString();
            }
            if (id) {
                found[id] = result;
            }
            for (key in encoded) {
                value = encoded[key];
                if (key !== idProperty) {
                    result[key] = doDecode(value);
                }
            }
            return result;
        };
        const decodeArray = function (encoded) {
            let value;
            return (function () {
                let i, len;
                const results = [];
                for (i = 0, len = encoded.length; i < len; i++) {
                    value = encoded[i];
                    results.push(doDecode(value));
                }
                return results;
            })();
        };
        if (encoded == null) {
            return encoded;
        }
        if (isArray(encoded)) {
            return decodeArray(encoded);
        }
        if (typeof encoded === 'object') {
            return decodeObject(encoded);
        }
        return encoded;
    };
    return doDecode(encoded);
};

JSOG.stringify = function (obj) {
    return JSON.stringify(JSOG.encode(obj));
};

JSOG.parse = function (str) {
    return JSOG.decode(JSON.parse(str));
};

if (typeof module !== 'undefined' && module.exports) {
    module.exports = JSOG;
}

[dfahlander]

Don't know if it could be of any value here, but I made a similar module for this that supports arrays as well as objects, typeson. Except for resolving cyclics, it can also encapsulate types.

[brettz9]

Looks very, very nice, @dfahlander , thanks! A couple questions...

Your code comments say:

Supports built-in types such as Date, Error, Regexp etc by default

...but your description of typeson-registry/presets/builtin (which doesn't appear to be run by default) mentions Error, RegExp, etc. We want such a the latter but want to throw on the former, so it'd be helpful to know whether the code comment is just outdated and one must, as it would appear, whitelist everything except for the default of cyclic objects.

As the appeal could go beyond this library, it'd be cool if one could flip a switch to get the Structured Cloning Algorithm support (including throwing upon invalid items). Hooks for handling unrecognized types could also be helpful.

Again, looks very nice...

[dfahlander]

Ah, it's an old comment. It doesn't support anything by default except cyclic references. Need to register each type that should be supported. The registry contains most javascript built-ins. Should add a preset for structured clone (where Error should not be included, but Image etc should). Would be very easy to add those types to the registry except for Blob which is asynchronic. The lib must probably be extended with an optional async api.

[brettz9]

I think one could force-load a Blob synchronously via XMLHttpRequest and binary, but synchronous XHR is already deprecated. In IndexedDB I think we should be loading synchronously anyways, as the specs expect synchronous reporting of clone errors, but again, doing so would be deprecated.

[dfahlander]

Would also need to add code to throw for unregistered types

[brettz9]

What happens now?

[dfahlander]

Very interesting. I can understand why browser vendors have been struggling with the blob support in indexedDB.

[dfahlander]

It just passes it to JSON.stringify ()

[brettz9]

Based on looking a bit at the spec and also testing with postMessage in Chrome, the following seems to mimic the Sca minus the Blobs:

const typeson = new Typeson().register([
    specialNumbers, primitiveObjects, date, regexp, arraybuffer, dataview, typedArrays, imagedata, intlTypes, map, set
]);

Until you add in an API for unrecognized types, I think we can just register one other type whose test function (the 0th item in the registered array) throws upon encountering a bad object.

I wish there were a cross-frame safe way to replace value.constructor === Object checks where warranted though.

(value.constructor === Object || {}.constructor.toString() === 'function Object() { [native code] }')

...might at least be a little more lenient even while Function.prototype.toString is mostly implementation-dependent.

[brettz9]

Oh, and although I see your code handles references between arrays and objects, I see there are a few cases which are problematic for me:

1. ~References which refer back to the variable itself at root.~
2. By using JSON.stringify, the identify of undefined gets lost or merged with null. It'd be important I think for us to have a string serialization (as we could store as a SQLite value) which preserved this distinction for faithful rebuilding during parsing (without a custom replacer, i.e., that there would be a default replacer that rebuilt the string with undefined; this could in turn be supplied to a parser whose reviver would similarly rebuild undefined (though a reviver unlike JSON.parse's which wouldn't give the undesired behavior upon undefined)).
3. Sparse arrays (e.g., var arr = new Array(5);) might perhaps need their own handling (which Object.keys(...).forEach would miss; at least, I see that encapsulate doesn't distinguish explicit undefined for which a key has been created from one just missing). typeson.encapsulate and Chrome with postMessage both clone the sparse length (and both treat undefined as implicit), but in Chrome, interestingly only if at least one property is set (e.g., arr[2] = 'xyz'; arr.length === 5;) and explicit undefined are not preserved as such. I'd see this as lower priority though, assuming Chrome is even behaving per spec or if this latter behavior is spec'd at all. I think we could get your code supporting it by removing the undefined check in if (val !== undefined) clone[key] = val;

[brettz9]

I've amended my reply as I see the root was not a problem and I added some observations about sparse arrays. So in short, the one big thing I'd like to see added (or working) is making analogues to stringify/parse which distinguish undefined and null (if not also implicit undefined in sparse arrays).

[dfahlander]

I hope to get some time next week. Also added you (@brettz9) as collaborator for typeson and typeson-registry. Feel free to make changes.

[brettz9]

Both issues can now be surmounted via typeson/typeson-registry on master. Thanks!

[dfahlander]

And thanks to you for improving typeson! Do you think typeson/typeson-registry is ready for a new npm publish? Do we have to bump major version (or are we backward compatible?)?

[brettz9]

Yes, I think we're ready (just added docs).

If you wanted to be really strict, typeson-registry might need a bumped major version since the builtin preset now preserves undefined after revival (which would instead become null before). You had mentioned though that you would continue to add ES6 items into the preset, so maybe it would be expected to expand (though undefined is of course pre-ES6). So otherwise, just minor version bumps with the new features re: undefined behavior.

If you are publishing an update to typeson-registry now, don't forget to bump the version of the typeson dependency too... So glad to find something which encodes types within objects simply, does so without eval, and offers a logical, cleanly extensible package system with some broad useful presets/types.

I can really see this use case of typeson recurring. Perhaps even in IndexedDB, as we're now using BSON/sockets in testing internally (with possible future public export) for our IndexedDB-capable Worker shim for Node and maybe we might want to reconstruct some objects crossing over processes.

[brettz9]

I just added one more set of changes to the typeson-registry, @dfahlander , if you wouldn't mind including those when you publish (I split into separate modules the Structured Cloning preset from the Structured Cloning preset which throws).

[brettz9]

Our cloning algorithm has been revised courtesy of typeson/typeson-registry, so cyclic values are fully supported in master (as are many other types supported by the algorithm; issues #285 and #286 tracking specific special types not currently supported). In the process our remaining dependency on eval was also removed. Thanks for everyone's help.

@axemclion , I am also sure appreciating the great work done in the Mocha tests which help a lot for coverage, going nicely with the W3C tests.