Design a variable store with placeholder substitution

01The design, in the six-step framework

1. Requirements and use cases

A program stores named variables whose values may refer to other variables, in the form PATH=%HOME%/bin. Reading a variable returns the fully expanded text, following references as deep as they go. A reference to a missing variable and a chain that loops back on itself are both reported clearly. Any template string can be expanded against the store. A literal percent sign is written %%.

Out of scope: reading the real process environment, default values inside the syntax, and shell features such as command substitution.

Constraints: reading is far more common than writing, so repeated expansion should be cheap; a later set must affect variables that refer to it; a malformed template is rejected at set time, when the person who wrote it is still present; and cycle errors show the whole chain.

2. Core entities and relationships

• VarStore: holds raw text, parsed parts and a memo of expanded values.
• Literal and Ref: the two kinds of part a template breaks into.
• tokenize: turns one template into a list of parts, with positioned errors.
• UnknownVariable, CycleError, TemplateError: three distinct failures, because a caller responds to each differently.

Variables refer to each other by name only, never by object. The store therefore holds an implicit directed graph in which each Ref is an edge, and expansion is a depth-first walk of that graph.

3. Interfaces and key methods

class VarStore:
    def set(self, key: str, value: str) -> None:
        """Store the raw template; a '%' literal is written '%%'."""
    def get(self, key: str) -> str:
        """Fully expanded value; raises UnknownVariable or CycleError."""
    def raw(self, key: str) -> str: ...
    def expand(self, template: str) -> str:
        """Expand any string against the store."""
    def delete(self, key: str) -> None: ...

Invariants: every key in _raw has a parsed entry; each memo entry equals the full expansion under the current variables, so any write clears the memo; get never returns text that still holds an unexpanded reference; a failed set leaves the store unchanged, because tokenizing happens before any assignment.

4. Design patterns and the choices behind them

Parse once, render many times

Repeated string replacement is the obvious approach, and it has a real bug: an expanded value that happens to contain %X% gets expanded again, and %% becomes ambiguous. Splitting the template into parts means expansion output is never re-scanned (see parsing and tokenizing). It also moves validation to set, and the error can carry an offset.

Cycle detection with the path, not a visited set

A cycle exists only when a variable appears on the current path. A plain visited set would raise a false alarm on a diamond, where A refers to B and C and both refer to D. Keeping the path as a list detects real loops and also gives the chain for the message: A -> B -> A.

Memo with blanket invalidation

The memo makes repeat reads a dictionary lookup, and shared sub-variables are computed once. On a write the whole memo is cleared. Tracking reverse dependencies and invalidating only the affected keys, as the spreadsheet does, is more precise and more code; for a store written rarely, clearing is the correct trade-off, and you should say so.

Named exceptions and a hook for missing keys

Some callers want strict failure and others want an empty string. Rather than a flag, the optional on_missing callable decides. The API stays one method with one default behaviour.

5. Core flow and code

1. set("HOME", "/home/ana") tokenizes to one Literal and clears the memo.
2. set("BIN", "%HOME%/bin") tokenizes to Ref("HOME") and Literal("/bin").
3. get("BIN") calls _resolve with an empty path; BIN joins the path, _render reaches the Ref and resolves HOME.
4. HOME has only a literal, so it renders directly and is memoised. BIN renders to /home/ana/bin and is memoised too.
5. set("A", "%B%") and set("B", "%A%") both succeed, since each is a valid template. get("A") walks A, B, then finds A on the path and raises CycleError with chain A, B, A.
6. set("C", "100%") raises TemplateError at offset 3 before anything is stored.

from __future__ import annotations
from dataclasses import dataclass
from typing import Callable

class UnknownVariable(KeyError):
    pass

class CycleError(ValueError):
    def __init__(self, chain: list[str]) -> None:
        super().__init__(" -> ".join(chain))
        self.chain = chain

class TemplateError(ValueError):
    def __init__(self, msg: str, pos: int) -> None:
        super().__init__(f"{msg} at offset {pos}")
        self.pos = pos

@dataclass(frozen=True)
class Literal:
    text: str

@dataclass(frozen=True)
class Ref:
    name: str

def tokenize(template: str) -> list:
    """Split into Literal and Ref parts. %% is a literal percent sign."""
    parts, buf, i = [], [], 0
    while i < len(template):
        ch = template[i]
        if ch != "%":
            buf.append(ch); i += 1
            continue
        if template[i + 1:i + 2] == "%":
            buf.append("%"); i += 2
            continue
        end = template.find("%", i + 1)
        if end == -1:
            raise TemplateError("unterminated placeholder", i)
        name = template[i + 1:end]
        if not name.replace("_", "").isalnum():
            raise TemplateError(f"bad variable name {name!r}", i)
        if buf:
            parts.append(Literal("".join(buf))); buf = []
        parts.append(Ref(name))
        i = end + 1
    if buf:
        parts.append(Literal("".join(buf)))
    return parts

class VarStore:
    def __init__(self, on_missing: Callable[[str], str] | None = None) -> None:
        self._raw: dict[str, str] = {}
        self._parsed: dict[str, list] = {}
        self._memo: dict[str, str] = {}
        self._on_missing = on_missing

    def set(self, key: str, value: str) -> None:
        self._parsed[key] = tokenize(value)        # reject bad templates before storing
        self._raw[key] = value
        self._memo.clear()

    def delete(self, key: str) -> None:
        self._raw.pop(key, None)
        self._parsed.pop(key, None)
        self._memo.clear()

    def raw(self, key: str) -> str:
        if key not in self._raw:
            raise UnknownVariable(key)
        return self._raw[key]

    def get(self, key: str) -> str:
        return self._resolve(key, [])

    def expand(self, template: str) -> str:
        return self._render(tokenize(template), [])

    def _resolve(self, key: str, stack: list[str]) -> str:
        if key in self._memo:
            return self._memo[key]
        if key in stack:                            # on the current path: a real cycle
            raise CycleError(stack[stack.index(key):] + [key])
        if key not in self._parsed:
            if self._on_missing is not None:
                return self._on_missing(key)
            raise UnknownVariable(key)
        stack.append(key)
        value = self._render(self._parsed[key], stack)
        stack.pop()
        self._memo[key] = value
        return value

    def _render(self, parts: list, stack: list[str]) -> str:
        out = []
        for part in parts:
            out.append(part.text if isinstance(part, Literal) else self._resolve(part.name, stack))
        return "".join(out)

6. Extensions, concurrency and what interviewers probe

• Reject cycles at set time: possible with a walk from the new references, as in the spreadsheet. The catch is that a cycle may be closed by a variable defined later, and the two-step scenario above shows why lazy detection is still needed for forward references.
• Depth: a chain of ten thousand variables overflows recursion; an explicit stack removes that, at a cost in readability.
• Thread safety: reads write to the memo, so concurrent get calls race on it. One lock is simplest; a read-write lock does not help unless the memo fill is separated from the read.
• Escaping: confirm the syntax with the interviewer. Asking what a bare percent means is exactly the type of question that shows care.
• Test first: plain value, one reference, nested references, diamond (no false cycle), direct self-reference, two-node cycle, missing variable, %%, unterminated placeholder, and a set that changes an already-memoised result.
• Common mistake: looping str.replace until nothing changes, which never terminates on a cycle and re-expands text that came from values.

02Where this question was reported

• Land the Lab · 'Expand placeholders from a variable store'
• PracHub · Google SWE; store class with placeholder resolution