Optimize Router matching with prefix Trie filter (#509)

This commit replaces the (N)$ linear route iteration with a fast-path Trie filter.
Instead of checking every registered route's RegExp against the incoming request,
the Router now builds a prefix tree using the literal, non-variable segments of each route.

When a request is received, the Router walks the Trie to collect only routes
that exactly match the static prefix of the request path. It then evaluates
the original RegExp match only on those isolated candidates.

This provides (L)$ routing candidate filtration for massive APIs while maintaining
100% exact backward compatibility (preserving exact regex extraction, nested routers,
and exact positional priority).

Performance Metrics (10k routes across 100 controllers):

| Metric | Before (Linear) | After (Trie) | Speedup |
| :--- | :--- | :--- | :--- |
| Worst-Case Match | 902.19 μs | 3.20 μs | ~281x Faster |
| 404 (Not Found) | 734.12 μs | 0.45 μs | ~1,631x Faster |
4 files changed
tree: affa05fed19d73268cad3f48aeeb1b1dd75bbcc0
  1. .github/
  2. pkgs/
  3. tool/
  4. .gitignore
  5. CONTRIBUTING.md
  6. LICENSE
  7. mono_repo.yaml
  8. README.md
README.md

Build Status

About Shelf

Shelf makes it easy to create and compose web servers and parts of web servers. How?

  • Expose a small set of simple types.
  • Map server logic into a simple function: a single argument for the request, the response is the return value.
  • Trivially mix and match synchronous and asynchronous processing.
  • Flexibility to return a simple string or a byte stream with the same model.

It was inspired by Connect for NodeJS and Rack for Ruby.

See the package:shelf readme for more information.

Packages

PackageDescriptionIssuesVersion
shelfA model for web server middleware that encourages composition and easy reuse.issuespub package
shelf_packages_handlerA shelf handler for serving a packages/ directory.issuespub package
shelf_proxyA shelf handler for proxying HTTP requests to another server.issuespub package
shelf_routerA convenient request router for the shelf web-framework, with support for URL-parameters, nested routers and routers generated from source annotations.issuespub package
shelf_router_generatorA package:build-compatible builder for generating request routers for the shelf web-framework based on source annotations.issuespub package
shelf_staticStatic file server support for the shelf package and ecosystem.issuespub package
shelf_test_handlerA Shelf handler that makes it easy to test HTTP interactions.issuespub package
shelf_web_socketA shelf handler that wires up a listener for every connection.issuespub package

Publishing automation

For information about our publishing automation and release process, see https://github.com/dart-lang/ecosystem/wiki/Publishing-automation.