Welcome, guest | Sign In | My Account | Store | Cart

This function recursively walks the items and values of two dict like objects. At each level when a key exists in both, and each value is a dict, then the destination dict is updated from the source dict usiing the builtin dict.update method. After the operation all keys and values from the source, at any level, will be referenced in the destination.

Python, 72 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def recursiveupdate(dst, src):
    """Recursively update dst from src.

    Recursion depth is bounded by the heap rather than the python 
    interpretor recursion limit.

    >>> dst = dict(a=1,b=2,c=dict(ca=31, cc=33, cd=dict(cca=1)), d=4, f=6)
    >>> src = dict(b='u2',c=dict(cb='u32', cd=dict(cda=dict(cdaa='u3411', cdab='u3412'))), e='u5')
    >>> r = recursiveupdate(dst, src)
    >>> assert r is dst
    >>> assert r['a'] == 1 and r['d'] == 4 and r['f'] == 6
    >>> assert r['b'] == 'u2' and r['e'] == 'u5'
    >>> assert dst['c'] is r['c']
    >>> assert dst['c']['cd'] is r['c']['cd']
    >>> assert r['c']['cd']['cda']['cdaa'] == 'u3411'
    >>> assert r['c']['cd']['cda']['cdab'] == 'u3412'
    >>> from pprint import pprint; pprint(r)
    {'a': 1,
     'b': 'u2',
     'c': {'ca': 31,
           'cb': 'u32',
           'cc': 33,
           'cd': {'cca': 1, 'cda': {'cdab': 'u3412', 'cdaa': 'u3411'}}},
     'd': 4,
     'e': 'u5',
     'f': 6}
    """
    irecursiveupdate(dst, src.iteritems())
    return dst

def irecursiveupdate(a, biter):
    """Recursively update dict `a` from `biter`

    `biter` is assumed to be an iterable of the form::
        [(k0, v0), (k1, v1), ..., (kN, vN)]

        ie, the result of src.iteritems()
    `a` is assumed to be a dict or dict like instance.

    In the following `dst` is the intial value of `a` and `src` is
    the initial value of `biter`.

    For every key in src: 
        If that key is also in dst and
        both dst[k] and src[k] are dicts then:
            recursiveupdate(dst[k], (src[k]))
        otherwise:
            dst[k] = src[k]

    """
    try:
        stack = []
        while biter:
            for (bk,bv) in biter:
                if (bk in a 
                    and isinstance(bv, dict)
                    and isinstance(a[bk], dict)):
                    stack.append((biter, a)) # current -> parent
                    break
                else:
                    a[bk] = bv
            else:
                while not biter:
                    biter, a = stack.pop() # current <- parent 
                continue
            biter, a = bv.iteritems(), a[bk]
    except IndexError:
        pass

if __name__ == '__main__':
    import doctest
    doctest.testmod()
 

A typical use of this recipe is for merging configuration, option and default value trees. Libraries like ConfgiObj support this sort of thing and a lot more besides. However, if all you want is a merge based on pythons dict.update semantics then this recipe may be all you need.

1 comment

Manuel Muradas 14 years, 6 months ago  # | flag

My version:

def merge_dictionary(dst, src):
    stack = [(dst, src)]
    while stack:
        current_dst, current_src = stack.pop()
        for key in current_src:
            if key not in current_dst:
                current_dst[key] = current_src[key]
            else:
                if isinstance(current_src[key], dict) and isinstance(current_dst[key], dict) :
                    stack.append((current_dst[key], current_src[key]))
                else:
                    current_dst[key] = current_src[key]
    return dst


if __name__ == '__main__':
    dst = dict(a=1,b=2,c=dict(ca=31, cc=33, cd=dict(cca=1)), d=4, f=6, g=7)
    src = dict(b='u2',c=dict(cb='u32', cd=dict(cda=dict(cdaa='u3411', cdab='u3412'))), e='u5', h=dict(i='u4321'))
    r = merge_dictionary(dst, src)
    assert r is dst
    assert r['a'] == 1 and r['d'] == 4 and r['f'] == 6
    assert r['b'] == 'u2' and r['e'] == 'u5'
    assert dst['c'] is r['c']
    assert dst['c']['cd'] is r['c']['cd']
    assert r['c']['cd']['cda']['cdaa'] == 'u3411'
    assert r['c']['cd']['cda']['cdab'] == 'u3412'
    assert r['g'] == 7
    assert src['h'] is r['h']

    from pprint import pprint
    pprint(r)
Created by Robin Bryce on Tue, 19 Dec 2006 (PSF)
Python recipes (4591)
Robin Bryce's recipes (1)

Required Modules

Other Information and Tasks