Merge a set of commits to track diffs

merge.py

local_commits = [
    {'hash': 11, 'diff': 'a'},
    {'hash': 12, 'diff': 'b'},
    {'hash': 20},
    {'hash': 13, 'diff': 'c'},
    {'hash': 14, 'diff': 'd'},
    {'hash': 15, 'diff': 'e'},
    {'hash': 16},
    {'hash': 17},
    {'hash': 18},
    {'hash': 19}
]

# To have:
# - inserted commit
# - reorder
# - removed
# - unchanged
# - changed

remote_commits = [
    {'hash': 100, 'diff': 'a'},
    {'hash': 101, 'diff': 'c'},
    {'hash': 102, 'diff': 'b'},
    {'hash': 103, 'diff': 'bb'},
    {'hash': 14, 'diff': 'd'},
    {'hash': 15, 'diff': 'e'}
]

merged = [
    {'hash': 11, 'diff': 'a', 'old': 100},
    {'hash': 12, 'diff': 'b', 'old': 102},
    {'hash': None, 'diff': 'bb', 'old': 103},
    {'hash': 20, 'diff': 'q'},
    {'hash': 13, 'diff': 'c', 'old': 101},
    {'hash': 14, 'diff': 'd'},
    {'hash': 15, 'diff': 'e'},
    {'hash': 16, 'diff': 'r'},
    {'hash': 17, 'diff': 's'},
    {'hash': 18, 'diff': 't'},
    {'hash': 19, 'diff': 'u'}
]

def getd(xs, i, default):
    try:
        return xs[i]
    except KeyError:
        return default


def new_id():
    import random
    return str(random.randint(1000, 2000))

def merge(heres, theres):
    there_ids = {}
    for i in range(len(theres)):
        there = theres[i]
        prv = theres[i-1]['diff'] if i-1 >= 0 else None
        nxt = theres[i+1]['diff'] if i+1 < len(theres) else None
        there_ids[there['diff']] = {
            'diff': there['diff'],
            'hash': there['hash'],
            'old': there.get('old', []),
            'prev': prv,
            'next': nxt,
        }
    
    merged = []

    for here in heres:
        if 'diff' not in here:
            # New commit inserted
            m = {
                'hash': here['hash'],
                'diff': new_id(),
                'old': [],
            }
        else:
            # Existing commit, just match
            there = there_ids.pop(here['diff'])
            m = {
                'hash': here['hash'],
                'diff': here['diff'],
                'old': [there['hash']] + there['old'],
            }
        merged.append(m)

    # Handle deleted commits
    for there_id, there in there_ids.items():
        if there['prev'] is not None:
            # Insert after parent
            for i in range(len(merged)):
                if merged[i]['diff'] == there['prev']:
                    merged.insert(i+1, {
                        'diff': there['diff'],
                        'hash': None,
                        'old': [there['hash']] + there['old']
                    })
                    break
            continue
        if there['nxt'] is not None:
            # Insert before child
            for i in range(len(merged)):
                if merged[i]['diff'] == there['nxt']:
                    merged.insert(i, {
                        'diff': there['diff'],
                        'hash': None,
                        'old': [there['hash']] + there['old']
                    })
                    break
            continue
        else:
            raise ValueError('No parent or child found for there id ...')

    return merged

import pprint
pprint.pprint(merge(local_commits, remote_commits))