[PR #442] [MERGED] perf: replace O(n) linear route matching with radix trie #575

New issue

Closed

opened 2026-05-06 13:08:50 +02:00 by BreizhHardware · 0 comments

BreizhHardware commented

2026-05-06 13:08:50 +02:00

Owner

📋 Pull Request Information

Original PR: https://github.com/cloudflare/vinext/pull/442
Author: @Divkix
Created: 3/11/2026
Status: ✅ Merged
Merged: 3/11/2026
Merged by: @james-elicx

Base: main ← Head: perf/route-matching-trie

📝 Commits (5)

1c9f2c5 perf: replace O(n) linear route matching with radix trie
b1de57a test: update entry-templates snapshot and assertion for trie-based matching
f284871 fix: address review comments on trie-based route matching
fc2823d fix: update matchRoute regex in test to match new 1-arg signature
0be0bf4 Merge branch 'main' into perf/route-matching-trie

📊 Changes

9 files changed (+745 additions, -248 deletions)

View changed files

📝 packages/vinext/src/entries/app-rsc-entry.ts (+13 -10)
📝 packages/vinext/src/entries/pages-server-entry.ts (+9 -34)
📝 packages/vinext/src/routing/app-router.ts (+16 -51)
📝 packages/vinext/src/routing/pages-router.ts (+16 -56)
➕ packages/vinext/src/routing/route-trie.ts (+195 -0)
📝 tests/__snapshots__/entry-templates.test.ts.snap (+59 -94)
📝 tests/entry-templates.test.ts (+3 -2)
➕ tests/route-trie.test.ts (+433 -0)
📝 tests/shims.test.ts (+1 -1)

📄 Description

Closes #444

Summary

Introduces a radix trie data structure (route-trie.ts) that replaces O(n) linear route scanning with O(depth) trie-based lookup for all route matching
Wired into all 4 codebases that share matching logic: pages-router.ts, app-router.ts, app-rsc-entry.ts (generated), and pages-server-entry.ts (generated)
Trie enforces correct precedence via traversal order (static > dynamic > catch-all > optional catch-all) with recursive DFS backtracking
matchPattern retained only in app-rsc-entry.ts for the intercept lookup (0-5 entries, not worth trie-ifying)

Test plan

59 new unit + parity tests in tests/route-trie.test.ts covering: static, dynamic, catch-all, optional catch-all, backtracking, malformed patterns, deeply nested routes, root routes, and full parity with linear matchPattern
171 existing routing tests pass (routing.test.ts, route-sorting.test.ts)
622 integration tests pass (app-router.test.ts, pages-router.test.ts, features.test.ts)
Typecheck, lint, format all clean
CI: full Vitest suite + Playwright E2E

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/cloudflare/vinext/pull/442 **Author:** [@Divkix](https://github.com/Divkix) **Created:** 3/11/2026 **Status:** ✅ Merged **Merged:** 3/11/2026 **Merged by:** [@james-elicx](https://github.com/james-elicx) **Base:** `main` ← **Head:** `perf/route-matching-trie` --- ### 📝 Commits (5) - [`1c9f2c5`](https://github.com/cloudflare/vinext/commit/1c9f2c5580fd87363cb90dba30f92b83e4e552c6) perf: replace O(n) linear route matching with radix trie - [`b1de57a`](https://github.com/cloudflare/vinext/commit/b1de57aed97e9f9957282c0d8e81d2d42ab4c571) test: update entry-templates snapshot and assertion for trie-based matching - [`f284871`](https://github.com/cloudflare/vinext/commit/f28487191219cfdc67276152d95fc0ec2210bcdb) fix: address review comments on trie-based route matching - [`fc2823d`](https://github.com/cloudflare/vinext/commit/fc2823d7532a94a0c7338e777babf0add90335b5) fix: update matchRoute regex in test to match new 1-arg signature - [`0be0bf4`](https://github.com/cloudflare/vinext/commit/0be0bf478722f57bf7fdc9bfaf3b0800ff69e764) Merge branch 'main' into perf/route-matching-trie ### 📊 Changes **9 files changed** (+745 additions, -248 deletions) <details> <summary>View changed files</summary> 📝 `packages/vinext/src/entries/app-rsc-entry.ts` (+13 -10) 📝 `packages/vinext/src/entries/pages-server-entry.ts` (+9 -34) 📝 `packages/vinext/src/routing/app-router.ts` (+16 -51) 📝 `packages/vinext/src/routing/pages-router.ts` (+16 -56) ➕ `packages/vinext/src/routing/route-trie.ts` (+195 -0) 📝 `tests/__snapshots__/entry-templates.test.ts.snap` (+59 -94) 📝 `tests/entry-templates.test.ts` (+3 -2) ➕ `tests/route-trie.test.ts` (+433 -0) 📝 `tests/shims.test.ts` (+1 -1) </details> ### 📄 Description Closes #444 ## Summary - Introduces a radix trie data structure (`route-trie.ts`) that replaces O(n) linear route scanning with O(depth) trie-based lookup for all route matching - Wired into all 4 codebases that share matching logic: `pages-router.ts`, `app-router.ts`, `app-rsc-entry.ts` (generated), and `pages-server-entry.ts` (generated) - Trie enforces correct precedence via traversal order (static > dynamic > catch-all > optional catch-all) with recursive DFS backtracking - `matchPattern` retained only in `app-rsc-entry.ts` for the intercept lookup (0-5 entries, not worth trie-ifying) ## Test plan - [x] 59 new unit + parity tests in `tests/route-trie.test.ts` covering: static, dynamic, catch-all, optional catch-all, backtracking, malformed patterns, deeply nested routes, root routes, and full parity with linear `matchPattern` - [x] 171 existing routing tests pass (`routing.test.ts`, `route-sorting.test.ts`) - [x] 622 integration tests pass (`app-router.test.ts`, `pages-router.test.ts`, `features.test.ts`) - [x] Typecheck, lint, format all clean - [x] CI: full Vitest suite + Playwright E2E --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>