Stepwise DNS resolver with aliasing

The spec used here. Each level is graded by a fixed harness, and later levels assume the earlier ones are right.

Clarify first. Does adding the same address twice duplicate it (no)? Should a cycle raise or return empty (empty here; real resolvers return SERVFAIL)? Does a wildcard match several labels (yes here, as long as nothing closer exists)? What TTL does an answer reached through aliases have (the smallest along the chain, because the answer is wrong as soon as any link changes)?

One normalization helper. Lowercase and strip the trailing dot in _norm, called on every input. Most hidden-test failures in this problem are normalization, not logic.

Resolution is a loop, not recursion. Start at the name; at each step look up its entry (exact first, then wildcards). An alias moves to its target; addresses end the walk. Keep a seen set and a hop counter: the set catches cycles at once, and the counter bounds long but acyclic chains. A loop with an explicit limit also avoids Python's recursion limit.

TTL along a chain. If www → web (ttl 300) and web → 10.0.0.1 (ttl 60), the answer 10.0.0.1 is only safe to cache for 60 seconds. ttl_left is the minimum of each link's remaining time, where remaining = expires_at - t.

Expiry is a read-time check. An entry with expires_at <= t is invisible. Because the alias-versus-address exclusivity rule must also respect expiry, add_record on a name whose alias has expired succeeds.

MAX_HOPS = 16


def _norm(name):
    return name.strip().lower().rstrip(".")


class Resolver:
    def __init__(self):
        self.addresses = {}  # name -> {ip: expires_at or None}
        self.aliases = {}    # name -> (target, expires_at or None)

    @staticmethod
    def _alive(expires_at, ts):
        return expires_at is None or ts < expires_at

    def _live_addresses(self, name, ts):
        return {ip: e for ip, e in self.addresses.get(name, {}).items() if self._alive(e, ts)}

    def _live_alias(self, name, ts):
        entry = self.aliases.get(name)
        return entry if entry and self._alive(entry[1], ts) else None

    def _entry(self, name, ts):
        """('alias', target, expires) | ('addresses', {ip: expires}) | None,
        trying the exact name, then the closest enclosing wildcard."""
        labels = name.split(".")
        candidates = [name] + ["*." + ".".join(labels[i:]) for i in range(1, len(labels))]
        for candidate in candidates:
            alias = self._live_alias(candidate, ts)
            if alias:
                return ("alias", alias[0], alias[1])
            found = self._live_addresses(candidate, ts)
            if found:
                return ("addresses", found)
        return None

    # -- writes --------------------------------------------------------------
    def add_record(self, name, ip, ts=0, ttl=None):
        name = _norm(name)
        if self._live_alias(name, ts):
            return False
        self.addresses.setdefault(name, {})[ip] = None if ttl is None else ts + ttl
        return True

    def add_alias(self, alias, target, ts=0, ttl=None):
        alias, target = _norm(alias), _norm(target)
        if alias == target or self._live_addresses(alias, ts):
            return False
        self.aliases[alias] = (target, None if ttl is None else ts + ttl)
        return True

    # -- reads ---------------------------------------------------------------
    def resolve(self, name, ts=0):
        return self.resolve_with_ttl(name, ts)[0]

    def resolve_with_ttl(self, name, ts=0):
        name, seen, ttl_left = _norm(name), set(), None

        def shorter(expires_at):
            if expires_at is None:
                return ttl_left
            left = expires_at - ts
            return left if ttl_left is None else min(ttl_left, left)

        for _ in range(MAX_HOPS + 1):
            if name in seen:
                return [], None  # cycle
            seen.add(name)
            entry = self._entry(name, ts)
            if entry is None:
                return [], None
            if entry[0] == "addresses":
                for expires_at in entry[1].values():
                    ttl_left = shorter(expires_at)
                return sorted(entry[1]), ttl_left
            _, name, expires_at = entry
            ttl_left = shorter(expires_at)
        return [], None  # chain too long

sorted on address strings is lexicographic (10.0.0.10 before 10.0.0.2). If the grader expects numeric order, sort with ipaddress.ip_address as the key; ask.

Let h be the chain length (at most 16), L the labels in a name and k the addresses on the final name.

• add_*: O(k) for the liveness check on the name, else O(1).
• resolve: O(h × L × k) in the worst case: each hop tries up to L wildcard candidates. With h ≤ 16 and L under 10 this is tiny.
• Space: O(entries).

1. Iterative resolution, the real "stepwise" part. A real resolver asks a root server, which refers it to the .com servers, which refer it to the domain's servers, which answer. Model each server as a resolver that returns either an answer or a referral (NS names plus their addresses, the "glue"), and loop with the same hop limit and cycle detection. Missing glue means resolving the name server's own name first, which is where loops come from.
2. Caching. Cache each link (alias or address set) separately with its own expiry, not the final answer, so a change to one link only invalidates that link. Cache negative answers too (NXDOMAIN), with their own shorter TTL, or a missing name gets hammered.
3. Concurrency. Many clients asking for the same uncached name should trigger one upstream query (request coalescing: a per-name future that later callers wait on).
4. Load balancing. Return the address list in rotated order per query (round-robin DNS), or weighted by health checks. Clients often take the first address, so order matters.
5. Wildcard edge cases. In real DNS a wildcard does not match a name that exists with other record types, and an empty non-terminal (a name that exists only because a child exists) blocks the wildcard. Say this to show you know the simplification.

Mid-level (L4)

• Gets Level 1 right with normalization, deduplication and sorted output.
• Follows alias chains and detects cycles.
• Applies expiry consistently.

Senior (L5)

• Writes resolution as a bounded loop with a seen set, and enforces alias-versus-address exclusivity with expiry taken into account.
• Explains and implements the chain TTL as the minimum over links.
• Implements closest-enclosing wildcards with exact names winning.

Staff (L6+)

• Describes iterative resolution with referrals and glue, and how loops arise there.
• Designs per-link and negative caching, request coalescing and load-balancing order.
• Knows where the model simplifies real DNS (wildcard rules, record types) and says so.