Trie-Based URL Router with Path Variables and Catch-All Tails

Build the routing table for a small web framework. Route templates are registered at startup. Then, for every incoming request, you look up the matching handler and pull the path variables out of the URL.

class Router:
    def add(self, template: str, handler) -> None: ...
    def match(self, path: str) -> tuple[object, dict[str, str]] | None: ...

Paths are split on / and empty segments are dropped, so /shops/42/ becomes ["shops", "42"] and / becomes []. Query strings have already been removed.

Part 1: literal and variable segments

A template segment is either a literal (shops) or a variable written {name}, which matches exactly one non-empty segment and captures it.

• Precedence: where a literal and a variable could both match at the same position, try the literal first.
• Backtracking: if the literal branch cannot complete the match further down, fall back to the variable branch.
• Conflicts: registering two templates with the same shape raises ValueError. Two templates have the same shape when they are equal after every variable name is replaced by a placeholder, so /shops/{id} and /shops/{shop} conflict.

r = Router()
r.add("/shops/featured", "featured")
r.add("/shops/featured/banner", "banner")
r.add("/shops/{shop}/items", "items")
r.add("/shops/{shop}/items/{item}", "item")

r.match("/shops/featured")        # ("featured", {})
r.match("/shops/42/items")        # ("items", {"shop": "42"})
r.match("/shops/featured/items")  # ("items", {"shop": "featured"})   <- backtracked
r.match("/shops/7/items/x9")      # ("item", {"shop": "7", "item": "x9"})
r.match("/shops")                 # None

Part 2: catch-all tail

Add {*name}, which may only be the last segment of a template. It matches one or more remaining segments and captures them joined with /. Precedence at any position is literal, then variable, then catch-all, with backtracking across all three.

r.add("/files/{*rest}", "files")
r.add("/files/{owner}/meta", "meta")
r.match("/files/a/b/c.txt")   # ("files", {"rest": "a/b/c.txt"})
r.match("/files/ann/meta")    # ("meta", {"owner": "ann"})
r.match("/files")             # None  (catch-all needs at least one segment)

Registering a {*name} anywhere other than the last segment raises ValueError.

Constraints

Up to 10^5 templates, and paths up to 50 segments long. A lookup should not scan every registered template. State the complexity of add and match.