Recursively combine dictionaries

Question

Alright, this is doing my head in. I have two dictionaries with object groups as shown below:

groups = {
    'servers': ['unix_servers', 'windows_servers'],
    'unix_servers': ['server_a', 'server_b', 'server_group'],
    'windows_servers': ['server_c', 'server_d'],
    'server_group': ['server_e', 'server_f']
}

hosts = {
    'server_a': '10.0.0.1',
    'server_b': '10.0.0.2',
    'server_c': '10.0.0.3',
    'server_d': '10.0.0.4',
    'server_e': '10.0.0.5',
    'server_f': '10.0.0.6'
}

The output I'm looking for is:

d3 = {
    'servers': {
        'unix_servers': {
            'server_a': '10.0.0.1',
            'server_b': '10.0.0.2',
            'server_group': {
                'server_e': '10.0.0.5',
                'server_f': '10.0.0.6'
            }
        },
        'windows_servers': {
            'server_c': '10.0.0.3',
            'server_d': '10.0.0.4'
        }
    }
}

The problem I'm having is that I don't know beforehand how much levels of recursion there are, as nested groups can theoretically go on infinitely. Additionally, I'm having trouble with determining which keys should be a top-level key in the combined dictionary.

I currently have the following:

def resolve(d1, d2):
for k, v in d1.items():
    for i in v:
        if i in d2.keys():
            d3[k] = {i: d2[i]}

This returns:

{
  "servers": {
    "unix_servers": {
      "server_a": "10.0.0.1",
      "server_b": "10.0.0.2",
      "server_group": {
        "server_e": "10.0.0.5",
        "server_f": "10.0.0.6"
      }
    },
    "windows_servers": {
      "server_c": "10.0.0.3",
      "server_d": "10.0.0.4"
    }
  },
  "unix_servers": {
    "server_b": "10.0.0.2"
  },
  "windows_servers": {
    "server_d": "10.0.0.4"
  },
  "server_group": {
    "server_f": "10.0.0.6"
  }
}

Which is close, but it's clearly missing recursion and doesn't handle nesting of keys. Mainly looking for pointers here, recursion logic doesn't click for me yet...

Answer 1

I think this does what you want:

def resolve(groups, hosts):
    # Groups that have already been resolved
    resolved_groups = {}
    # Group names that are not root
    non_root = set()
    # Make dict with resolution of each group
    result = {}
    for name in groups:
        result[name] = _resolve_rec(name, groups, hosts, resolved_groups, non_root)
    # Remove groups that are not root
    for name in groups:
        if name in non_root:
            del result[name]
    return result

def _resolve_rec(name, groups, hosts, resolved_groups, non_root):
    # If group has already been resolved finish
    if name in resolved_groups:
        return resolved_groups[name]
    # If it is a host finish
    if name in hosts:
        return hosts[name]
    # New group resolution
    resolved = {}
    for child in groups[name]:
        # Resolve each child
        resolved[child] = _resolve_rec(child, groups, hosts, resolved_groups, non_root)
        # Mark child as non-root
        non_root.add(child)
    # Save to resolved groups
    resolved_groups[name] = resolved
    return resolved

With your example:

groups = {
    'servers': ['unix_servers', 'windows_servers'],
    'unix_servers': ['server_a', 'server_b', 'server_group'],
    'windows_servers': ['server_c', 'server_d'],
    'server_group': ['server_e', 'server_f']
}

hosts = {
    'server_a': '10.0.0.1',
    'server_b': '10.0.0.2',
    'server_c': '10.0.0.3',
    'server_d': '10.0.0.4',
    'server_e': '10.0.0.5',
    'server_f': '10.0.0.6'
}

d3 = {
    'servers': {
        'unix_servers': {
            'server_a': '10.0.0.1',
            'server_b': '10.0.0.2',
            'server_group': {
                'server_e': '10.0.0.5',
                'server_f': '10.0.0.6'
            }
        },
        'windows_servers': {
            'server_c': '10.0.0.3',
            'server_d': '10.0.0.4'
        }
    }
}


print(resolve(groups, hosts) == d3)
# True

Note this can fall into infinite recursion for malformed inputs, if you have for example group A containing group B but then group B contains group A.

Answer 2

Assuming you're ok with possibly having cross referencing data structure, you don't necessarily need to use recursion here.

from itertools import chain

group_dicts = {k: {} for k in groups}

for g in group_dicts:
    for child_key in groups[g]:
        child = group_dicts.get(child_key, hosts.get(child_key))
        group_dicts[g][child_key] = child

# remove entries that are referenced at least once
not_top_levels = set(chain.from_iterable(groups.values()))
result = {g: group_dicts[g] for g in group_dicts if g not in not_top_levels}

Unlike other solutions, this will correctly handle cycles and infinitely recursive groups, as all the dict references are shared. When your groups topologically describes a tree, this will work exactly the same as the recursive solution. However, if your groups topologically describes a directed acyclic graph, this solution would share the dicts for all the nodes that appears more than once, while the recursive solution would copy and expand the duplicates out into a regular tree, this wouldn't really be an issue if you don't need to mutate the dicts. If your groups topologically describes a graph with cycles, then this will create those cycles, while the recursive solution would fall due to infinite recursion.

Answer 3

You can use simple recursion:

def build(val): 
  return {i:build(i) for i in groups[val]} if val in groups else hosts[val]

---

import json
print(json.dumps({'servers':build('servers')}, indent=4))

Output:

{
  "servers": {
    "unix_servers": {
        "server_a": "10.0.0.1",
        "server_b": "10.0.0.2",
        "server_group": {
            "server_e": "10.0.0.5",
            "server_f": "10.0.0.6"
        }
    },
    "windows_servers": {
        "server_c": "10.0.0.3",
        "server_d": "10.0.0.4"
     }
  }
}