Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMike Gerwitz <gerwitzm@lovullo.com>2017-01-27 15:42:16 -0500
committerMike Gerwitz <gerwitzm@lovullo.com>2017-01-30 00:29:25 -0500
commit24180e704aaec8b1610a24d1f76ba66e70e97b02 (patch)
treedeeeccbe2283f6fc7cdd0a36d4c2fe22ed8282f9
parent3289e42003f311cb819a2b3ba20910a6e043902b (diff)
downloadliza-24180e704aaec8b1610a24d1f76ba66e70e97b02.tar.gz
liza-24180e704aaec8b1610a24d1f76ba66e70e97b02.tar.bz2
liza-24180e704aaec8b1610a24d1f76ba66e70e97b02.zip
Add DiffStore
* src/store/DiffStore.js: Add class. * test/store/DiffStoreTest.js: Add test case. DEV-2296
-rw-r--r--src/store/DiffStore.js293
-rw-r--r--test/store/DiffStoreTest.js235
2 files changed, 528 insertions, 0 deletions
diff --git a/src/store/DiffStore.js b/src/store/DiffStore.js
new file mode 100644
index 0000000..539738f
--- /dev/null
+++ b/src/store/DiffStore.js
@@ -0,0 +1,293 @@
+/**
+ * Store that lazily computes diffs since last change
+ *
+ * Copyright (C) 2017 LoVullo Associates, Inc.
+ *
+ * This file is part of the Liza Data Collection Framework
+ *
+ * Liza is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+"use strict";
+
+const Class = require( 'easejs' ).Class;
+const Store = require( './Store' );
+const StoreMissError = require( './StoreMissError' );
+
+
+/**
+ * Lazily compute diffs since last change
+ *
+ * This store recursively calculates the diff of scalars and
+ * objects. Unlike many other stores, you don't always get out what you put
+ * in.
+ *
+ * There are three operations:
+ * - `#add` stages a change to a key;
+ * - `#get` calculates the diff of a key against its committed value; and
+ * - `#clear` commits staged values, clearing all diffs.
+ *
+ * Values are recursively compared until a scalar is found. If the scalar
+ * matches the committed value, it is recognized as unchanged and
+ * represented as `undefined`. Otherwise, the staged value takes its
+ * place.
+ *
+ * @example
+ * // Promise resolving to [ undefined, "quux" ]
+ * DiffStore()
+ * .add( 'foo', [ "bar", "baz" ] )
+ * .then( store => store.clear() )
+ * .add( 'foo', [ "bar", "quux" ] )
+ * .then( store => store.get( 'foo' ) )
+ *
+ * // Promise resolving to { foo: undefined, baz: [ undefined, 'c' ] }
+ * DiffStore()
+ * .add( 'foo', { foo: 'bar', baz: [ 'a', 'b', ] } )
+ * .then( store => store.clear() )
+ * .add( 'foo', { baz: [ 'a', 'c' ] } )
+ * .then( store => store.get( 'foo' ) )
+ *
+ * The union of all keys of all objects are included in the diff:
+ *
+ * @example
+ * // Promise resolving to { foo: undefined, baz: 'quux' }
+ * DiffStore()
+ * .add( 'foo', { foo: 'bar' } )
+ * .then( store => store.clear() )
+ * .add( 'foo', { baz: 'quux' } )
+ * .then( store => store.get( 'foo' ) )
+ *
+ * Values are diff'd since the last `#clear`, so adding a value multiple
+ * times will compare only the last one:
+ *
+ * @example
+ * // Promise resolving to undefined
+ * DiffStore()
+ * .add( 'foo', 'foo' )
+ * .then( store => store.clear() )
+ * .add( 'foo', 'bar' )
+ * .add( 'foo', 'baz' )
+ * .add( 'foo', 'foo' )
+ * .then( store => store.get( 'foo' ) )
+ *
+ * // Promise resolving to undefined
+ * DiffStore()
+ * .add( 'foo', 'bar' )
+ * .then( store => store.clear() )
+ * .then( store => store.get( 'foo' ) )
+ *
+ * One caveat: since the diff represents the absence of changes as
+ * `undefined`, there is no way to distinguish between an actual undefined
+ * value and a non-change. If this is important to you, you can subtype
+ * this class and override `#diff`.
+ *
+ * For more examples, see the `DiffStoreTest` test case.
+ */
+module.exports = Class( 'DiffStore' )
+ .implement( Store )
+ .extend(
+{
+ /**
+ * New data staged for committing
+ * @type {Object}
+ */
+ 'private _staged': {},
+
+ /**
+ * Previous values
+ * @type {Object}
+ */
+ 'private _commit': {},
+
+
+ /**
+ * Proxy item with value `value` to internal store matching against `key`
+ *
+ * Note that the key stored may be different than `key`. This
+ * information is important only if the internal stores are not
+ * encapsulated.
+ *
+ * @param {string} key store key to match against
+ * @param {*} value value for key
+ *
+ * @return {Promise.<Store>} promise to add item to store, resolving to
+ * self (for chaining)
+ */
+ 'virtual public add'( key, value )
+ {
+ this._staged[ key ] = value;
+
+ return Promise.resolve( this.__inst );
+ },
+
+
+ /**
+ * Retrieve diff of `key`
+ *
+ * This performs a lazy diff of the data `D` behind `key`. For each
+ * scalar value in `D`, recursively, the value will be `undefined` if
+ * there is no change and will be the staged value if changed. A change
+ * occurs when the data `D` differs from the value of `key` before the
+ * last `#clear`. A value is staged when it has been added since the
+ * last `#clear`.
+ *
+ * @param {string} key store key
+ *
+ * @return {Promise} promise for the key value
+ */
+ 'virtual public get'( key )
+ {
+ if ( ( this._staged[ key ] || this._commit[ key ] ) === undefined )
+ {
+ return Promise.reject(
+ StoreMissError( `Key '${key}' does not exist` )
+ );
+ }
+
+ return Promise.resolve(
+ this.diff( this._staged[ key ], this._commit[ key ] )
+ );
+ },
+
+
+ /**
+ * Commit staged data and clear diffs
+ *
+ * All staged data will be committed. Until some committed key `k` has
+ * its data modified via `#add`, `k` will not be considered to have
+ * changed.
+ *
+ * @return {Promise.<Store>} promise to add item to store, resolving to
+ * self (for chaining)
+ */
+ 'virtual public clear'()
+ {
+ Object.keys( this._staged ).forEach(
+ key => this._commit[ key ] = this._staged[ key ]
+ );
+
+ this._staged = {};
+
+ return Promise.resolve( this.__inst );
+ },
+
+
+ /**
+ * Recursively diff two objects or scalars `data` and `orig`
+ *
+ * A datum in `data` is considered to be changed when it is not equal to
+ * the corresponding datum in `orig`. If the datum is an object, it is
+ * processed recursively until a scalar is reached for comparison.
+ *
+ * The algorithm processes the union of the keys of both `data` and
+ * `orig`.
+ *
+ * One caveat: since the diff represents the absence of changes as
+ * `undefined`, there is no way to distinguish between an actual
+ * undefined value and a non-change. If this is important to you, you
+ * can override this method.
+ *
+ * An example of the output of the algorithm is given in the class-level
+ * documentation.
+ *
+ * @param {*} data new data
+ * @param {*} orig original data to diff against
+ *
+ * @return {*} diff
+ */
+ 'virtual protected diff'( data, orig )
+ {
+ if ( orig === undefined )
+ {
+ // no previous, then data must be new, and so _is_ the diff
+ return data;
+ }
+ else if ( typeof data !== 'object' )
+ {
+ // only compare scalars (we'll recurse on objects)
+ return ( data === orig )
+ ? undefined
+ : data;
+ }
+
+ const keys = this._getKeyUnion( data, orig );
+ let diff = ( Array.isArray( data ) ) ? [] : {};
+
+ for ( let key of keys )
+ {
+ diff[ key ] = this.diff( data[ key ], orig[ key ] );
+ }
+
+ return diff;
+ },
+
+
+ /**
+ * Calculate the union of the keys of `first` and `second`
+ *
+ * `first` and `second` must both be of type `object`.
+ *
+ * @param {*} first some object
+ * @param {*} second some object
+ *
+ * @return {Set} Object.keys(first) ∪ Object.keys(second)
+ */
+ 'private _getKeyUnion'( first, second )
+ {
+ const keys = new Set( Object.keys( first ) );
+
+ Object.keys( second )
+ .forEach( key => keys.add( key ) );
+
+ return keys;
+ },
+
+
+ /**
+ * Fold (reduce) all staged values
+ *
+ * A value is staged when it has been set but `#clear` has not yet
+ * been called---these are the only values that might be
+ * different. Since the purpose of this Store is to produce diffs,
+ * there is no way to iterate over all values previously encountered.
+ *
+ * The order of folding is undefined.
+ *
+ * The ternary function `callback` is of the same form as
+ * {@link Array#reduce}: the first argument is the value of the
+ * accumulator (initialized to the value of `initial`; the second
+ * is the stored item; and the third is the key of that item.
+ *
+ * @param {function(*,*,string=)} callback folding function
+ * @param {*} initial initial value for accumulator
+ *
+ * @return {Promise} promise of a folded value (final accumulator value)
+ */
+ 'public reduce'( callback, initial )
+ {
+ return Promise.resolve(
+ Object.keys( this._staged).reduce(
+ ( accum, key ) => {
+ const value = this.diff(
+ this._staged[ key ],
+ this._commit[ key ]
+ );
+
+ return callback( accum, value, key );
+ },
+ initial
+ )
+ );
+ },
+} );
diff --git a/test/store/DiffStoreTest.js b/test/store/DiffStoreTest.js
new file mode 100644
index 0000000..cfefcb3
--- /dev/null
+++ b/test/store/DiffStoreTest.js
@@ -0,0 +1,235 @@
+/**
+ * Test case for DiffStore
+ *
+ * Copyright (C) 2017 LoVullo Associates, Inc.
+ *
+ * This file is part of the Liza Data Collection Framework
+ *
+ * Liza is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+"use strict";
+
+const store = require( '../../' ).store;
+const chai = require( 'chai' );
+const expect = chai.expect;
+const Class = require( 'easejs' ).Class;
+const Sut = store.DiffStore;
+const StoreMissError = store.StoreMissError;
+
+chai.use( require( 'chai-as-promised' ) );
+
+
+describe( 'store.DiffStore', () =>
+{
+ it( 'considers first add call to be diffable', () =>
+ {
+ return expect(
+ Sut()
+ .add( 'foo', 'bar' )
+ .then( sut => sut.get( 'foo' ) )
+ ).to.eventually.equal( 'bar' );
+ } );
+
+
+ it( 'does not clear diff on add of new key', () =>
+ {
+ return expect(
+ Sut()
+ .add( 'foo', 'bar' )
+ .then( sut => sut.add( 'baz', 'quux' ) )
+ .then( sut => Promise.all( [
+ sut.get( 'foo' ),
+ sut.get( 'baz' ),
+ ] ) )
+ ).to.eventually.deep.equal( [ 'bar', 'quux'] );
+ } );
+
+
+ it( 'updates diff when key modified before clear', () =>
+ {
+ return expect(
+ Sut()
+ .add( 'foo', 'bar' )
+ .then( sut => sut.add( 'foo', 'baz' ) )
+ .then( sut => sut.get( 'foo' ) )
+ ).to.eventually.equal( 'baz' );
+ } );
+
+
+ it( 'considers key unchanged in diff immediately after clear', () =>
+ {
+ debugger;
+ return expect(
+ Sut()
+ .add( 'foo', 'bar' )
+ .then( sut => sut.clear() )
+ .then( sut => sut.get( 'foo' ) )
+ ).to.eventually.equal( undefined );
+ } );
+
+
+ // distinction between unknown key and no change (compare to above test)
+ it( 'distinguishes between unchanged and unknown keys', () =>
+ {
+ debugger;
+ return expect(
+ Sut()
+ .add( 'foo', 'bar' )
+ .then( sut => sut.clear() )
+ .then( sut => sut.get( 'unknown' ) )
+ ).to.eventually.be.rejectedWith( StoreMissError );
+ } );
+
+
+ [
+ // scalar
+ {
+ orig: 'bar',
+ next: 'baz',
+ expected: 'baz',
+ },
+
+ {
+ orig: [ 'bar', 'baz' ],
+ next: 'baz',
+ expected: 'baz',
+ },
+
+ // returns new value if entire array changed
+ {
+ orig: [ 'bar', 'baz' ],
+ next: [ 'quux', 'quuux' ],
+ expected: [ 'quux', 'quuux' ],
+ },
+
+ // sets unchanged indexes to undefined
+ {
+ orig: [ 'bar', 'baz', 'quux' ],
+ next: [ 'bar', 'quux' ],
+ expected: [ undefined, 'quux', undefined ],
+ },
+
+ // next size > original
+ {
+ orig: [ 'bar', 'baz' ],
+ next: [ 'quux', 'baz', 'quuux' ],
+ expected: [ 'quux', undefined, 'quuux' ],
+ },
+
+ // 5 ^
+
+ // same
+ {
+ orig: [ 'bar', 'baz' ],
+ next: [ 'bar', 'baz' ],
+ expected: [ undefined, undefined ],
+ },
+
+ // no longer an array
+ {
+ orig: [ 'bar', [ 'baz', 'quux' ] ],
+ next: [ 'bar', 'quux' ],
+ expected: [ undefined, 'quux'],
+ },
+
+ // nested change
+ {
+ orig: [ 'bar', [ 'baz', 'quux' ] ],
+ next: [ 'bar', [ 'foo', 'quux' ] ],
+ expected: [ undefined, [ 'foo', undefined ] ],
+ },
+
+ // note that it always recurses to set undefined, even if all of
+ // them are undefined
+ {
+ orig: [ [ 'bar' ], [ [ 'baz', 'quux' ] ] ],
+ next: [ [ 'bar' ], [ [ 'baz', 'foo' ] ] ],
+ expected: [ [ undefined ], [ [ undefined, 'foo' ] ] ],
+ },
+
+ // there's not a distinction in the algorithm between numeric
+ // indexes and object keys
+ {
+ orig: { foo: 'bar' },
+ next: { foo: 'baz' },
+ expected: { foo: 'baz' },
+ },
+
+ // 10 ^
+
+ {
+ orig: { foo: 'bar' },
+ next: { foo: 'bar' },
+ expected: { foo: undefined },
+ },
+ {
+ orig: { foo: 'bar', baz: 'quux' },
+ next: { foo: 'foo', baz: 'quux' },
+ expected: { foo: 'foo', baz: undefined },
+ },
+ {
+ orig: { foo: 'bar', baz: 'quux' },
+ next: { baz: 'change' },
+ expected: { foo: undefined, baz: 'change' },
+ },
+ {
+ orig: { foo: 'bar', baz: [ 'a', 'b', ] },
+ next: { baz: [ 'a', 'c' ] },
+ expected: { foo: undefined, baz: [ undefined, 'c' ] },
+ },
+ {
+ orig: { foo: { bar: [ 'baz' ] } },
+ next: { foo: { bar: [ 'baz', 'quux' ] } },
+ expected: { foo: { bar: [ undefined, 'quux' ] } },
+ },
+ ].forEach( ( { orig, next, expected }, i ) =>
+ {
+ it( `properly diffs (${i})`, () =>
+ {
+ return expect(
+ Sut()
+ .add( 'foo', orig )
+ .then( sut => sut.clear() )
+ .then( sut => sut.add( 'foo', next ) )
+ .then( sut => sut.get( 'foo' ) )
+ ).to.eventually.deep.equal( expected );
+ } );
+ } );
+
+
+ describe( '#reduce', () =>
+ {
+ it( 'iterates though each diff', () =>
+ {
+ return expect(
+ Sut()
+ .add( 'foo', [ 'a', 'foo' ] )
+ .then( sut => sut.add( 'bar', 'b' ) )
+ .then( sut => sut.add( 'baz', 'c' ) )
+ .then( sut => sut.clear() )
+ .then( sut => sut.add( 'foo', [ 'a2', 'foo' ] ) )
+ .then( sut => sut.add( 'baz', 'c2' ) )
+ .then( sut => sut.reduce( ( accum, value, key ) =>
+ {
+ accum[ key ] = value;
+ return accum;
+ }, {} ) )
+ ).to.eventually.deep.equal( {
+ foo: [ 'a2', undefined ],
+ baz: 'c2',
+ } );
+ } );
+ } );
+} );