Using JSON.stringify for deep comparison is unstable

[parkerault]

elastic-composer/src/history.ts

Line 202 in a21862c

JSON.stringify(newHistoryLocation) !==

I'm not sure if this has caused any problems yet, but it raises some concerns. JSON.stringify processes keys in order of insertion (see rfc), so it's inherently unstable. A more reliable solution would be to compute a hash for each state and use that for comparison instead. There are also a few packages that implement a stable JSON.stringify but I don't know about quality/reliability.

[dearsaturn]

Oh yeah, I definitely mentioned this once upon a time. Here's how I fixed it in a cache class I made for API calls (it sucks):

    set = async (key, value) => {
        const encodedKey = this.encodeKeyToString(key);
        const multi = this.redisClient.multi();
        multi.set(encodedKey, stringify(value));
        multi.expire(encodedKey, this.ttlMilliseconds / 1000);
        await multi.exec();
    };
    encodeKeyToString = (key) => {
        if (typeof key === 'string') {
            return key;
        }

        return `fbgraph-cache:${stringify(this.sortObject(key))}`;
    };

    sortObject = (obj) => {
        // eslint-disable-next-line no-nested-ternary
        return obj === null || typeof obj !== 'object'
            ? obj
            : Array.isArray(obj)
            ? obj.map(this.sortObject)
            : Object.assign(
                  {},
                  ...Object.entries(obj)
                      .sort(([keyA], [keyB]) => keyA.localeCompare(keyB))
                      .map(([k, v]) => ({[k]: this.sortObject(v)}))
              );
    };

And this only really helps for height = 1 objects.

[parkerault]

If you just want to keep an ordered history you can do

this.history = new Map().set(someHash(firstState), firstState));
/* some time later */
const [lastStateHash] = Array.from(this.history.keys()).slice(-1);
const newStateHash = someHash(newState);
if (newStateHash !== lastStateHash) this.history.set(newStateHash, newState);

In practice you can probably get away with doing the same thing in a plain object since most recent engines follow the spec, but it's making an assumption that the code is running in a certain environment. Using a WeakMap may be a better approach depending on how transient the history object is.

If the goal is to prevent duplicates a Set will do. Of course if the code is not in a hot path you can just calculate the hash every time.

Edit: if you don't want to use fancy stuff you could keep a separate array of ordered hash cursors and an index of objects keyed by hash.

[dearsaturn]

A hash package

[erhathaway]

Thanks for bringing up this issue! JSON.stringyify is used all over the place for deep object comparison. I support fixing this - I think whatever solution is fastest at doing comparison should be used.

Also, my first instinct is that this hasn't caused many problems b/c (I think) most object construction is predictable? Outside the History API, the end result of this would probably be extra side effects being put on the queue. I think I added side effect deduplication and throttling to the side effect processing queue, so the library might make it so problems don't manifest...?

Either way, it would be good to fix!

[parkerault]

I this module most of the instances are used in a way where the insertion order will be the same, so it's more of a suggestion than a bug report. :)