Comparison API #138

Open
kitsonk opened this Issue Mar 30, 2016 · 8 comments

Projects

None yet

5 participants

@kitsonk
Member
kitsonk commented Mar 30, 2016

Several functional problems have highlighted that core could benefit from a centralised API for comparing objects and mutating objects based upon those comparisons. We should have an API that:

  • Compares two objects/arrays/iterables? and provides a diff between the two, which would be a simple JavaScript object which then can be easily serialised and persisted.
  • Take a set of comparison records and applies/patches them to an object.
@pottedmeat pottedmeat was assigned by kitsonk Mar 30, 2016
@kitsonk kitsonk added the enhancement label Mar 30, 2016
@kitsonk kitsonk added this to the beta.2 milestone Mar 30, 2016
@kitsonk kitsonk modified the milestone: 2016.04, beta.2 Apr 8, 2016
@kitsonk
Member
kitsonk commented Apr 12, 2016

@pottedmeat has been working on this in the compare branch.

@pottedmeat

I've come up with what I think is a fairly robust API for object/array patch creation that has some areas of ambiguity that I need to nail down.

The first is with the object patch which has change records at each key indicated whether it was added, updated, or deleted. It also provides the old and new value at that key.

  • For objects values, is reference comparison sufficient?
  • For array values, should we compare length and contents (just by primitive/reference)?
  • Should newValue contain object and array values?
  • Should array values be duplicated before being assigned to newValue

Next is the array patch, which stores the indexes at which changes will be made as well as what's been added and removed and whether these changes were relocated within that array. This lets us learn a lot about the changes, find previous/next references, and do intelligent object removal/movement.

Values are stored as indexes. This is acceptable for the original array, but the references to the comparison array mean that the comparison array cannot be mutated and it must be passed when performing a patch. This seems problematic.

Previous/next references can be computed (either the position before the insertion point or the insertion point plus the number of removed items) but it's not immediately evident.

  • Should we store values or duplicate the comparison array and keep a reference to it?
  • Should we store previous/next references?
  • If we store previous/next references, should we store the old or the new value or both?
  • Should we even worry about storing these extra references?
@kitsonk kitsonk modified the milestone: 2016.05, 2016.04 May 3, 2016
@kitsonk kitsonk modified the milestone: 2016.06, 2016.05 Jun 7, 2016
@kitsonk kitsonk modified the milestone: 2016.06, 2016.07 Jul 4, 2016
@kitsonk
Member
kitsonk commented Jul 18, 2016

@matt-gadd, @agubler as we discussed, if you could look at the compare branch let's figure out how this fits in and how we can land it into core.

@kitsonk
Member
kitsonk commented Jul 18, 2016

I just had an epiphany on this. This is a perfect situation for ES Observables.

If diff offered up an observable interface and patch could consume one, then that would add a lot of future flexibility.

@matt-gadd
Contributor

as @pottedmeat notes the ArrayPatch patch syntax is problematic - having to pass the comparison array kind of defeats the purpose of having diff in the first place, and makes the patch itself unportable. If we stored the values we'd also be able to reverse/inverse the patch and it feels like a solid goal of a diff/patch library to support reversible patches.

This may be more related to the dojo/stores#4 but there are quite a few JSONPatch libs out there (i've used https://github.com/cujojs/jiff in the past), did we take a look at any? or did we deem it not flexible enough for a generic diff/patch util?

On the compare code itself, unless i'm missing something it appears that patch doesn't correctly support both ArrayPatch's and ObjectPatch's, due to the operation ordering (ArrayPatch before ObjectPatch).

example failing test:

'can remove item from an array, and change an item': () => {
    const myOpts = { identityKey: 'id', compareObjects: true };
    const myArray = [
        { id: 1, label: 'foo' },
        { id: 2, label: 'bar' }
    ];
    const myArray2 = [
        { id: 2, label: 'qux' }
    ];
    const myPatch = diff(myArray, myArray2, myOpts);
    const myResult = patch(myArray, myPatch, myArray2);
    // above throws, as the object to change no longer exists at that array index
    assert.equal(myResult, myArray2);
}
@kitsonk
Member
kitsonk commented Jul 19, 2016

I am open to revisiting this. Also, before Google abandoned it, the specification for Harmony Observe and the related polyfills covered off mutations of objects and arrays in a fairly efficient fashion. I made an attempt quite a while ago to fit a lot of that into a Dojo-like core: https://github.com/kitsonk/core-js/tree/master/observe The test may also be useful: https://github.com/kitsonk/core-js/tree/master/tests/unit/observe

@kitsonk
Member
kitsonk commented Jul 19, 2016

In regards to JSONPatch I am not opposed to it.

The one challenge though that I see with it, for array operations it isn't very efficient. This was a challenge with the Harmony Object.observe as well and the way they solved it was via a splice record type (operation in JSONPatch terms). In addition, they allowed high-order transforms to be registered which could then more complex mutations. This is documented here: http://wiki.ecmascript.org/doku.php?id=harmony:observe_api_usage

If we adopted JSONPatch, but enhanced it to allow splices and potentially registrable change types, is it JSONPatch anymore?

@kitsonk kitsonk modified the milestone: 2016.07, 2016.08 Aug 1, 2016
@kitsonk kitsonk removed this from the 2016.08 milestone Oct 4, 2016
@kitsonk
Member
kitsonk commented Oct 4, 2016

We should close this down for the beta. @maier49 this relates to needs for dojo/stores.

@dylans dylans added this to the 2016.11 milestone Nov 9, 2016
@kitsonk kitsonk self-assigned this Nov 18, 2016
@dylans dylans modified the milestone: 2016.11, 2016.12 Dec 5, 2016
@dylans dylans modified the milestone: 2017.01, 2016.12 Dec 20, 2016
@kitsonk kitsonk was unassigned by dylans Dec 20, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment