Dictionary & list difference. Two-way and three-way.

difftools.py

from copy import deepcopy


def two_way_list_diff(left, right):
    """ Compares two lists, returns a tuple of two lists detailing
        which items have been added to the second list and removed
        from the first list.
        
        Example
        -------
        
           >>> two_way_list_diff(['foo', 'bar'], ['bar', 'baz'])
           (['baz'], ['foo'])
    """
    
    added = []
    removed = []
    for i in set(left + right):
        if i not in right:
            removed.append(i)
        if i not in left:
            added.append(i)
            
    return added, removed
    

def two_way_dict_diff(left, right):
    """ Compares two dictionaries and returns a tuple of dictionaries
        containing additions, changes and deletions.
    """
    
    additions = {}
    changes = {}
    deletions = {}
    
    for k in set(left)+set(right):
        if k not in left:
            additions[k] = right[k]
            continue
        if k not in right:
            deletions[k] = left[k]
            continue
        if left[k]!=right[k]:
            changes[k] = right[k]
            
    return additions, changes, deletions
        

def three_way_dict_diff(base, left, right):
    """ Compare a two dictionaries to a common baseline and return a
        tuple of the result of a three-way diff, a dictionary of any
        conflicts and a dictionary of changes made to achieve the diff
        in the form of keys mapping to tuples of previous values and
        new values.
        
        Examples
        --------
        
        No changes
        
          >>> base = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> right = {'foo': 'bar',
          ...          'baz': 'qux'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar', 'baz': 'qux'}, {}, {})
        
        
        Delete from one
        
          >>> base = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> right = {'foo': 'bar'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar'}, {}, {'baz': ('qux', None)})
        
        
        Delete from both
        
          >>> base = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> left = {'foo': 'bar'}
          >>> right = {'foo': 'bar'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar'}, {}, {'baz': ('qux', None)})
        
        
        Change in one, delete in the other
        
          >>> base = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'quux'}
          >>> right = {'foo': 'bar'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar', 'baz': 'qux'}, {'baz': ('quux', None)}, {})
        
        
        Change in both to different values
        
          >>> base = {'foo': 'bar'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'quux'}
          >>> right = {'foo': 'bar',
          ...          'baz': 'qux'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar'}, {'baz': ('quux', 'qux')}, {})
        
        
        Change in both to the same value
        
          >>> base = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'quux'}
          >>> right = {'foo': 'bar',
          ...          'baz': 'quux'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar', 'baz': 'quux'}, {}, {'baz': ('qux', 'quux')})
          
        
        Add in both with the same value
        
          >>> base = {'foo': 'bar'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> right = {'foo': 'bar',
          ...          'baz': 'qux'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar', 'baz': 'qux'}, {}, {'baz': (None, 'qux'})
          
        
        Add in one
        
          >>> base = {'foo': 'bar'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> right = {'foo': 'bar'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar', 'baz': 'qux'}, {}, {'baz': (None, 'qux'})
          
        
        Add in both with different values
        
          >>> base = {'foo': 'bar'}
          >>> left = {'foo': 'bar',
          ...         'baz': 'qux'}
          >>> right = {'foo': 'bar',
          ...          'baz': 'quux'}
          >>> three_way_dict_diff(base, left, right)
          ({'foo': 'bar'}, {'baz': ('qux', 'quux')}, {})
        
    """
    
    la, lc, ld = two_way_dict_diff(base, left)
    ra, rc, rd = two_way_dict_diff(base, right)
    
    result = deepcopy(base)
    
    changes = {}
    
    conflicts = {}
    
    all_additions = set(la)+set(ra)
    all_changes = set(lc)+set(rc)
    all_deletions = set(ld)+set(rd)
    
    for k in all_additions:
        if k in la and k in ra and la[k]!=ra[k]:
            # Added in both but with different values
            conflicts[k] = (left.get(k), right.get(k))
            continue
        
        elif k in la and k in ra and la[k]==ra[k] or \
             k in la:
            changes[k] = (None, left[k])
            result[k] = left[k]
            continue
            
        elif k in ra:
            changes[k] = (None, right[k])
            result[k] = right[k]
            continue
    
    for k in all_deletions:    
        if k in all_changes:
            conflicts[k] = (left.get(k), right.get(k))
            continue
        
        else:
            # deleted from one or both
            changes[k] = (result[k], None)
            del result[k]
            continue
            
    for k in all_changes:
        if k in all_deletions:
            # already dealt with this in the deletion loop.
            continue
        
        elif k in lc and k in rc and lc[k]!=rc[k]:
            # conflicting changes to both
            conflicts[k] = (left.get(k), right.get(k))
            continue
        
        elif k in lc:
            # implicitly "or k in lc and k in rc"
            changes[k] = (result[k], left[k])
            result[k] = left[k]
        else:
            changes[k] = (result[k], right[k])
            result[k] = right[k]
            
    return result, conflicts, changes