from typing import Dict
from io import StringIO


def interpolate(s: str, registers: Dict) -> str:
    """
    Interpolates variables in a string with values from a supplied dictionary of registers.

    The parser is very lax and will not interpolate variables that don't exist, as users
    may not be intending to interpolate a variable when they type the hash character.
    The hash symbols can be escaped with a caret (^), but if a caret is placed before
    a character that doesn't need escaping (another caret or a hash character), then
    the escape character acts as a normal character (nothing is removed or replaced).

    Parameters
    ----------
    s : str
        The string to interpolate
    registers : Dict[str, Message]
        A mapping of variable names to messages

    Returns
    -------
    str
        A new string with interpolated values

    """
    escaping = False
    variable_mode = False
    buffer = StringIO()
    variable_buffer = StringIO()
    for i in range(0, len(s)):
        if escaping:
            if s[i] != "#":
                buffer.write("^")
            buffer.write(s[i])
            escaping = False
        elif variable_mode:
            if s[i] == "#":
                name = variable_buffer.getvalue()
                if name in registers:
                    buffer.write(registers[name].content)
                else:
                    buffer.write("#")
                    buffer.write(name)
                    buffer.write("#")
                variable_buffer = StringIO()
                variable_mode = False
            elif s[i] != " ":
                variable_buffer.write(s[i])
            else:  # invalid variable name
                buffer.write("#")
                buffer.write(variable_buffer.getvalue())
                buffer.write(s[i])
                variable_buffer = StringIO()
                variable_mode = False
        elif s[i] == "^":
            escaping = True
        elif s[i] == "#":
            variable_mode = True
        else:
            buffer.write(s[i])
    if escaping:
        buffer.write("^")
    if len(variable_buffer.getvalue()):
        buffer.write("#")
        buffer.write(variable_buffer.getvalue())
    return buffer.getvalue()