Add functions for computing diff between two states (singer-io#54)

mdelaurentis · web-flow · commit a4437184b7ed · 2017-11-15T15:00:37.000-05:00
* Working on state diffing

* Use tuples

* Working on statediff

* Cleanup

* Correct docstring

* Pylint
diff --git a/singer/statediff.py b/singer/statediff.py
@@ -0,0 +1,70 @@
+import collections
+
+# Named tuples for holding add, change, and remove operations
+Add = collections.namedtuple('Add', ['path', 'newval'])
+Change = collections.namedtuple('Change', ['path', 'oldval', 'newval'])
+Remove = collections.namedtuple('Remove', ['path', 'oldval'])
+
+def paths(data, base=None):
+    '''Walk a data structure and return a list of (path, value) tuples, where
+    each path is the path to a leaf node in the data structure and the
+    value is the value it points to. Each path will be a tuple.
+
+    '''
+    if base is None:
+        base = ()
+
+    result = []
+    if isinstance(data, dict):
+        for key, val in sorted(data.items()):
+            result.extend(paths(val, base + (key,)))
+
+    elif isinstance(data, list):
+        for i, val in enumerate(data):
+            result.extend(paths(val, base + (i,)))
+
+    elif base:
+        result.append((base, data))
+
+    return result
+
+def diff(oldstate, newstate):
+    '''Compare two states, returning a list of Add, Change, and Remove
+    objects.
+
+    Add(path, newval) means path exists in newstate but not oldstate and
+    its value in newstate is newval.
+
+    Change(path, oldval, newval) means that path exists in both oldstate
+    and newstate but has different values. oldval is the val in oldstate
+    and newval is the value in newstate.
+
+    Remove(path, oldval) means the path exists in oldstate but not in
+    newstate, and the value in oldstate is oldval.
+
+    '''
+
+    # Convert oldstate and newstate from a deeply nested dict into a
+    # single-level dict, mapping a path to a value.
+    olddict = {k: v for (k, v) in paths(oldstate)}
+    newdict = {k: v for (k, v) in paths(newstate)}
+
+    # Build the list of all paths in both oldstate and newstate to iterate
+    # over.
+    all_paths = set()
+    all_paths.update(set(olddict.keys()))
+    all_paths.update(set(newdict.keys()))
+
+    result = []
+    for path in sorted(all_paths):
+        if path in olddict:
+            if path in newdict:
+                if olddict[path] == newdict[path]:
+                    pass # Don't emit anything if values are the same
+                else:
+                    result.append(Change(path, olddict[path], newdict[path]))
+            else:
+                result.append(Remove(path, olddict[path]))
+        else:
+            result.append(Add(path, newdict[path]))
+    return result
diff --git a/tests/test_statediff.py b/tests/test_statediff.py
@@ -0,0 +1,105 @@
+import unittest
+import singer.statediff as statediff
+from singer.statediff import Add, Remove, Change
+
+class TestPaths(unittest.TestCase):
+
+    def test_simple_dict(self):
+
+        self.assertEqual(
+            [(('a',), 1),
+             (('b',), 2)],
+            statediff.paths({'a': 1, 'b': 2}))
+
+    def test_nested_dict(self):
+        self.assertEqual(
+            [(('a', 'b'), 1),
+             (('a', 'c'), 2),
+             (('d', 'e'), 3)],
+            statediff.paths(
+                {
+                    'a': {
+                        'b': 1,
+                        'c': 2
+                    },
+                    'd': {
+                        'e': 3
+                    }
+                }
+            )
+        )
+            
+
+    def test_simple_array(self):
+        self.assertEqual(
+            [((0,), 'blue'),
+             ((1,), 'green')],
+            statediff.paths(
+                ['blue', 'green']))
+
+    def test_nested_array(self):
+        self.assertEqual(
+            [((0, 0), 'blue'),
+             ((0, 1), 'red'),
+             ((1, 0), 'green')],
+            statediff.paths([['blue', 'red'], ['green']]))
+
+    def test_arrays_in_dicts(self):
+        self.assertEqual(
+            [(('a', 0), 'blue'),
+             (('a', 1), 'red'),
+             (('b', 0), 'green')],
+            statediff.paths(
+                {
+                    'a': ['blue', 'red'],
+                    'b': ['green']
+                }
+            )
+        )
+
+    def test_none(self):
+        self.assertEqual([], statediff.paths(None))
+                
+class TestDiff(unittest.TestCase):
+
+    def test_add(self):
+        self.assertEqual(
+            [Add(('a',), 1),
+             Add(('b',), 2)],
+            statediff.diff({}, {'a': 1, 'b': 2}))
+
+    def test_remove(self):
+        self.assertEqual(
+            [Remove(('a',), 1),
+             Remove(('b',), 2)],
+            statediff.diff({'a': 1, 'b': 2}, {}))
+
+    def test_change(self):
+        self.assertEqual(
+            [Change(('a',), 1, 100),
+             Change(('b',), 2, 200)],
+            statediff.diff({'a': 1, 'b': 2},
+                           {'a': 100, 'b': 200}))
+                           
+    def test_null_input_for_old(self):
+        self.assertEqual(
+            [Add(('a',), 1)],
+            statediff.diff(None, {'a': 1}))
+
+    def test_null_input_for_new(self):
+        self.assertEqual(
+            [Remove(('a',), 1)],
+            statediff.diff({'a': 1}, None))
+
+    def test_null_input_for_both(self):
+        self.assertEqual([], statediff.diff(None, None))
+
+    def test_null_at_leaf(self):
+        self.assertEqual(
+            [Change(('a',), 1, None),
+             Change(('b',), None, 2)],
+            statediff.diff({'a': 1, 'b': None},
+                           {'a': None, 'b': 2}))
+
+
+        
