#! /usr/bin/python

import re

r = re.compile(r'((?:[^{]+|\{\{)*)\{([^}]*)\}')

def sub(tmpl, d):
    def f(m):
        return m.group(1) + d[m.group(2)]

    return r.sub(f, tmpl)

for tmpl, d, want in (
        ('', {}, ''),
        ('foo', {}, 'foo'),
        ('{', {}, '{'),
        ('}', {}, '}'),
        ('{{', {}, '{{'),
        ('}}', {}, '}}'),
        ('{}', {'': '✓'}, '✓'),
        ('a{b{c}d', {'b{c': '✓'}, 'a✓d'),
        ('a{b}}c}d', {'b': '✓'}, 'a✓}c}d'),   # `}}' isn't escaping `}'.
        ('a{{bc {d.e.f} }}{{{...} z', {'d.e.f': 'def', '...': 'etc'}, 'a{{bc def }}{{etc z'),
    ):
    got = sub(tmpl, d)
    if got != want:
        print(tmpl, d, want, got)