CODEWITHSUNDEEP
pythonrecursion
Alex Poca
Alex Poca

Reputation: 2566

How to expand dictionaries using recursion

To simplify a complex configuration everything is stored in a dictionary. Some parts of the configuration are repeated multiple times and it is error-prone to copy and paste them, even because they are subject to frequent changes.

To avoid this repetition, inside the dictionary there are some keys (beginning with '_') that groups common parameters together: i.e.

{
    ....
    "_common_settings": {
        val1: 0,
        val2: 1,
    }
    ....
}

Somewhere else this group of settings can be called by:

{
    ...
    "extra": "_common_settings"
    ...
}

The tricks is done by the extra key: every time it is found, it will be replaced by its definition. It appears only as a dictionary key and is not managed if it is a list element.

The whole config can be a mix of dictionaries and lists, with dictionaries in dictionaries or any other combination and any depth.

This is a short example of initial configuration:

initial_cfg = {

    # -------------------------------------------------------------------
    # common definitions

    "_other_common_params": {
        "fields": "all",
        "polling": 5
    },

    "_extra_params100": {
        "ip": "10.1.0.1",
        "name": "db100",
        "extra": "_other_common_params"
    },

    "_extra_params200": {
        "ip": "10.1.0.2",
        "name": "db200",
        "extra": "_other_common_params"
    },

    # -------------------------------------------------------------------
    # page-specific definitions

    "id101": {
        "db": [
            {   "id": "id101",
                "table": "table101",
                "extra": "_extra_params100"
            }
        ]
    },

    "id201": {
        "db": [
            {   "id": "id201",
                "table": "table201",
                "extra": "_extra_params200"
            },

            {   "id": "id202",
                "table": "table202",
                "extra": "_extra_params200"
            }
        ]
    }
}

and this is the final I would like to obtain (with the keys beginning with _ removed because they are useless):

final_cfg = {

    "id101": {
        "db": [
            {   "id": "id101",
                "table": "table101",
                "ip": "10.1.0.1",
                "name": "db100",
                "fields": "all",
                "polling": 5,
            }
        ]
    },

    "id201": {
        "db": [
            {   "id": "id201",
                "table": "table201",
                "ip": "10.1.0.2",
                "name": "db200",
                "fields": "all",
                "polling": 5
            },

            {   "id": "id202",
                "table": "table202",
                "ip": "10.1.0.2",
                "name": "db200",
                "fields": "all",
                "polling": 5             
            }
        ]
    }
}

I am in trouble with this recursive substitution because, according to the order in which the initial_config is processed the result changes and some extra are left around in final_config.

This is the code I am using now. Recursion is not my bread and I cannot fix it to manage a whole decoding of the initial_config.

def init_pages_config():

    global pages_config

    def rebuild_pages_config(branch):
        if type(branch) is list:
            # in lists simple recursion, no substitution
            for b in branch:
                rebuild_pages_config(b)

        elif type(branch) is dict:
            # in dictionaries substitution, then recursion
            if "extra" in branch:
                key = branch["extra"]
                del branch["extra"]
                branch.update(pages_config[key])

            for b in branch:
                rebuild_pages_config(branch[b])

    rebuild_pages_config(pages_config)

    # remove the entries beginning with _ 
    new_dict = {}
    for pc in pages_config.keys():
        if not pc.startswith("_"):
            new_dict[pc] = pages_config[pc]
    pages_config = new_dict

    from pprint import pprint
    pprint(pages_config)

Upvotes: 0

Views: 70

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1122342

You need to first process your _extra mappings. These form a graph, you could use a queue to ensure they are expanded fully:

from collections import deque
from itertools import chain
from functools import singledispatch

def expand_config(config):
    extras = build_substitutions(config)
    return substitute_recurse(config, extras)

def build_substitutions(config):
    substitutions = {}
    queue = deque((k, o.copy()) for k, o in config.items() if k[0] == '_')
    while queue:
        key, subst = queue.pop()
        if 'extra' in subst:
            if subst['extra'] not in substitutions:
                # extra keys not yet processed
                queue.appendleft((key, subst))
                continue
            subst.update(substitutions[subst.pop('extra')])
        substitutions[key] = subst
    return substitutions

@singledispatch
def substitute_recurse(obj, extras):
    return obj

@substitute_recurse.register(dict)
def _dict(d, extras):
    extra = extras.get(d.get('extra'), {})
    return {k: substitute_recurse(v, extras) 
            for k, v in chain(d.items(), extra.items())
            if k[0] != '_' and k != 'extra'}

@substitute_recurse.register(list)
def _list(l, extras):
    return [substitute_recurse(v, extras) for v in l]

The recursion is all handled by using single dispatch, which makes each per-type handler a lot simpler.

Upvotes: 2

Related Questions