Edge Gateway: Route Matching, 405s, Canaries and Rewrites

Edge Gateway: Route Matching, 405s, Canaries and Rewrites

You've joined the Edge Platform team, which owns the routing table of the company's API gateway. Last week's incident review (INC-4417) traced three customer-visible failures to the matcher, and three follow-ups are queued behind the fixes. The gateway is a small Python service; your job is to make match answer exactly as specified below, one Part at a time. The tests call run(operations).

Codebase

Operations

run(operations) executes the operations in order against a fresh gateway and returns one result per operation. An operation is [name, *args]. Admin failures are returned as "error: <code>" strings, never raised. Unknown names return "error: unknown operation"; an empty operation or a wrong number of arguments returns "error: invalid arguments".

Routes. method is GET, HEAD, POST, PUT, PATCH, DELETE, OPTIONS or ANY (any method), case-insensitive. A pattern starts with / and is a list of segments:

• a literal (users), compared case-insensitively;
• a param :name, which captures exactly one non-empty segment;
• a wildcard *name, only as the *last* segment, which captures everything that is left.

Names match [a-z_][a-z0-9_]* and are unique within a pattern. One trailing / is ignored and / is the root. Empty segments, and % or ? inside a literal, are bad pattern. Two routes *conflict* when they have the same method and the same shape (param and wildcard names ignored, literals compared case-insensitively): GET /a/:x and GET /A/:y/ conflict, GET /a/:x and ANY /a/:x do not.

Responses (match always returns one of these):

params holds one entry per param, in pattern order, with the decoded text; a wildcard maps to the list of its decoded segments (possibly empty). Existing code is the reference for anything not spelled out here: start with patterns.py and routes.py.

Part 1: Fix the matcher (INC-4417)

Goal: make match pick the right route and handle paths the way the rules below say. The matcher currently takes the first route in registration order that fits. The incident reports:

1. GET /users/me was served by the /users/:id route because it had been registered first.
2. A request for /static/a%2Fb was split into two segments, so it skipped the one-segment /static/:file route and was handled by a catch-all instead. Security wants an encoded slash to never create a segment.
3. GET /Users/42/ and GET /files (for a /files/*rest route) returned 404.

Rules (checked in this order)

1. The request method is case-insensitive and must be one of the seven real methods (ANY is not a request method), else 400 bad method.
2. The path must be a string that starts with /, else 400 bad path.
3. Everything from the first ? onwards (the query string) is ignored when matching.
4. If the path is longer than / and ends with /, exactly one trailing / is removed. The rest is split on / into segments; / has no segments. Empty segments are kept, so /a//b has three.
5. Then each segment is percent-decoded, once (%2F becomes a / character *inside* that segment, %252F becomes the text %2F). A % not followed by two hex digits, bytes that are not valid UTF-8, or a decoded NUL character make the whole request 400 bad path. + stays +.
6. A literal matches a segment if they are equal ignoring case. A param matches any non-empty segment and keeps its case. A wildcard matches zero or more remaining segments. Without a wildcard the pattern and the path need the same number of segments.
7. Candidates are the routes whose method equals the request method or is ANY and whose pattern fits. The winner is the candidate that is best by this list, in this order:
8. more literal segments;
9. no wildcard over a wildcard;
10. fewer params;
11. an exact method over ANY;
12. earlier registration.

No candidate: 404.

Example

[["route", "user-by-id", "GET", "/users/:id", "users"],
 ["route", "user-me", "GET", "/users/me", "profile"],
 ["route", "user-files", "GET", "/users/:id/files/*path", "files"],
 ["match", "GET", "/users/me"],
 ["match", "GET", "/Users/42/"],
 ["match", "GET", "/users/42/files/reports/2024%2Fq1.csv"],
 ["match", "GET", "/users"],
 ["match", "BREW", "/users"]]

returns

[true, true, true,
 {"status": 200, "route": "user-me", "upstream": "profile", "params": {}},
 {"status": 200, "route": "user-by-id", "upstream": "users", "params": {"id": "42"}},
 {"status": 200, "route": "user-files", "upstream": "files", "params": {"id": "42", "path": ["reports", "2024/q1.csv"]}},
 {"status": 404},
 {"status": 400, "error": "bad method"}]

tests/test_api.py::test_literal_route_beats_param_route_registered_earlier currently fails.

Part 2: 405s, HEAD, removal, and a table that scales (INC-4452)

Goal: teach the gateway to say *"right path, wrong method"*, serve HEAD from GET routes, let operators remove routes, and keep lookups fast on very large tables.

Rules (these replace Part 1's "no candidate means 404" and extend rule 7)

1. HEAD. A GET route can also serve a HEAD request. For the "method" step of the precedence list, a route's method is ranked: exact method (best), then ANY, then GET standing in for HEAD. Everything else in the list is unchanged.
2. 405. If no route can serve the request method, but at least one route's pattern fits the path (for some method), the answer is {"status": 405, "allow": [...]}. allow lists every method that *would* be served on this path, always in this order: GET, HEAD, POST, PUT, PATCH, DELETE, OPTIONS. An ANY route allows all seven; a GET route allows GET and HEAD. If no pattern fits the path, it is still 404; malformed requests are still 400.
3. Method is only a tie-break (list item 4). A less specific route that serves the method beats a more specific one that does not: with POST /a/b and GET /a/:x, GET /a/b is served by /a/:x.
4. unroute forgets the route completely: its id and its shape can be registered again, and a route registered again counts as newly registered for the "earlier registration" tie-break. Anything attached to the route (Part 3) goes with it.
5. Scale. ["route_many", count, id_template, method, pattern_template, upstream_template] registers count routes, replacing {i} (0-based) in each template, and returns count. ["load_test", method, path_template, count] resolves count requests ({i} replaced by 0..count-1) and returns {"statuses": {"200": n, ...}, "checksum": c} (statuses sorted by key; the checksum covers each individual answer, so any single wrong route or allow list changes it). Hidden tests register thousands of routes and resolve thousands of requests in one run, in well under the few seconds the suite has. A scan over all routes per request is too slow.

Example

[["route", "report", "GET", "/reports/:id", "reports"],
 ["route", "report-new", "POST", "/reports", "reports-write"],
 ["route", "report-pdf", "ANY", "/reports/:id/pdf", "pdf"],
 ["match", "HEAD", "/reports/9"],
 ["match", "DELETE", "/reports/9"],
 ["match", "PUT", "/reports"],
 ["match", "GET", "/reports"],
 ["match", "OPTIONS", "/reports/9/pdf"],
 ["match", "GET", "/nothing"],
 ["unroute", "report"],
 ["match", "GET", "/reports/9"],
 ["unroute", "report"],
 ["route", "report", "GET", "/reports/:id", "reports-v2"],
 ["match", "HEAD", "/reports/9"]]

returns

[true, true, true,
 {"status": 200, "route": "report", "upstream": "reports", "params": {"id": "9"}},
 {"status": 405, "allow": ["GET", "HEAD"]},
 {"status": 405, "allow": ["POST"]},
 {"status": 405, "allow": ["POST"]},
 {"status": 200, "route": "report-pdf", "upstream": "pdf", "params": {"id": "9"}},
 {"status": 404},
 true,
 {"status": 404},
 "error: unknown route",
 true,
 {"status": 200, "route": "report", "upstream": "reports-v2", "params": {"id": "9"}}]

Part 3: Canaries and rewrites (PLAT-9120)

Goal: let a route send some requests to a different upstream (a canary), and tell the upstream a different path than the one the client used. match now takes optional request headers.

Header names are case-insensitive (a request never has two names that differ only in case); values are compared exactly.

Canaries. rules is a list that replaces the route's rules ([] clears them). Each rule is exactly one of:

• {"upstream": u, "header": name, "equals": value}: applies when the request has that header and its value is exactly value (value may be the empty string);
• {"upstream": u, "percent": p}: applies when the request has a non-empty X-User-Id header and bucket(route_id, user_id) < p (bucket is in hashing.py). p is an integer from 0 to 100, so 0 never applies and 100 applies to every request that has a user id.

upstream and header are non-empty strings, equals is a string; anything else, including extra or missing keys or a non-list rules, is bad canary. The first rule, in list order, that applies decides the upstream in the response; a rule that does not apply never blocks later ones. If none applies, the route's own upstream is used. Canaries only choose the upstream: they never change which route is selected.

Rewrites. template starts with / and may contain {name} placeholders, where name is one of the route's param or wildcard names; any other use of { or } is bad rewrite. null removes the rewrite. When the matched route has a rewrite, the 200 body gets a final key "target":

1. Each placeholder is replaced by its value with every character except A-Z a-z 0-9 - . _ ~ written as %XX (UTF-8, uppercase hex). The captured values were decoded when the request was matched, so this puts the encoding back: the segment a/b becomes a%2Fb, never a/b. A wildcard is its segments encoded one by one and joined with / (no segments gives an empty string).
2. If any substituted value, or any segment of a substituted wildcard, is exactly . or .., the answer is {"status": 400, "error": "bad target"} instead. Placeholders that are not in the template are not checked.
3. If the request had a non-empty query string, ? and the original query string, byte for byte, are appended.

Routes without a rewrite have no "target" key, and 400, 404 and 405 bodies are unchanged. Parts 1 and 2 behave as before: unroute also removes a route's canary rules and rewrite.

Example

[["route", "search", "GET", "/api/:version/search/*terms", "search-v1"],
 ["canary", "search", [{"upstream": "search-beta", "header": "X-Beta", "equals": "on"},
                       {"upstream": "search-v2", "percent": 100}]],
 ["rewrite", "search", "/internal/{version}/q/{terms}"],
 ["match", "GET", "/api/v3/search/red%2Fblue/shoes?page=2"],
 ["match", "GET", "/api/v3/search/shoes", {"x-beta": "on", "X-User-Id": "kim"}],
 ["match", "GET", "/api/v3/search", {"X-USER-ID": "kim"}],
 ["match", "GET", "/api/v3/search/%2E%2E/admin"],
 ["match", "POST", "/api/v3/search"]]

returns

[true, true, true,
 {"status": 200, "route": "search", "upstream": "search-v1",
  "params": {"version": "v3", "terms": ["red/blue", "shoes"]}, "target": "/internal/v3/q/red%2Fblue/shoes?page=2"},
 {"status": 200, "route": "search", "upstream": "search-beta",
  "params": {"version": "v3", "terms": ["shoes"]}, "target": "/internal/v3/q/shoes"},
 {"status": 200, "route": "search", "upstream": "search-v2",
  "params": {"version": "v3", "terms": []}, "target": "/internal/v3/q/"},
 {"status": 400, "error": "bad target"},
 {"status": 405, "allow": ["GET", "HEAD"]}]

Notes

• Python 3 standard library only. Output must be deterministic.
• errors.py, responses.py, models.py, config.py and hashing.py are known-good.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later Parts must not break earlier ones; hidden tests re-check earlier behaviour after later features.
• Parts 1-2 is a solid result; Part 3 rounds it out.