wayfind

A speedy, flexible router for Rust.

Why another router?

Real-world projects often need advanced routing: inline parameters, mid-route wildcards, or compatibility with frameworks like Ruby on Rails and specifications like the OCI Distribution Specification.

wayfind aims to be competitive with the fastest routers while supporting these features. Unused features don't impact performance.

Showcase

[dependencies]
wayfind = "*"

use std::error::Error;

use wayfind::RouterBuilder;

let mut builder = RouterBuilder::new();
builder.insert("/v2", "end-1")?;
builder.insert("/v2/<*name>/blobs/<algorithm>:<hash>", "end-2")?;
builder.insert("/v2/<*name>/manifests/<reference>", "end-3")?;
builder.insert("/v2/<*name>/blobs/uploads", "end-4a")?;
builder.insert("/v2/<*name>/blobs/uploads/<reference>", "end-5")?;
builder.insert("/v2/<*name>/tags/list", "end-8a")?;
builder.insert("/v2/<*name>/referrers/<algorithm>:<hash>", "end-12a")?;

let router = builder.build();

let search = router.search("/v2").unwrap();
assert_eq!(search.data(), &"end-1");
assert_eq!(search.parameters(), &[]);

let search = router.search("/v2/myorg/myrepo/blobs/sha256:2c26b46b68ff").unwrap();
assert_eq!(search.data(), &"end-2");
assert_eq!(search.parameters(), &[
    ("name", "myorg/myrepo"),
    ("algorithm", "sha256"),
    ("hash", "2c26b46b68ff"),
]);

let search = router.search("/v2/myorg/myrepo/manifests/latest").unwrap();
assert_eq!(search.data(), &"end-3");
assert_eq!(search.parameters(), &[
    ("name", "myorg/myrepo"),
    ("reference", "latest"),
]);

let search = router.search("/v2/myorg/myrepo/blobs/uploads").unwrap();
assert_eq!(search.data(), &"end-4a");
assert_eq!(search.parameters(), &[
    ("name", "myorg/myrepo"),
]);

let search = router.search("/v2/myorg/myrepo/blobs/uploads/e361beb4-576f").unwrap();
assert_eq!(search.data(), &"end-5");
assert_eq!(search.parameters(), &[
    ("name", "myorg/myrepo"),
    ("reference", "e361beb4-576f"),
]);

let search = router.search("/v2/myorg/myrepo/tags/list").unwrap();
assert_eq!(search.data(), &"end-8a");
assert_eq!(search.parameters(), &[
    ("name", "myorg/myrepo"),
]);

let search = router.search("/v2/myorg/myrepo/referrers/sha256:2c26b46b68ff").unwrap();
assert_eq!(search.data(), &"end-12a");
assert_eq!(search.parameters(), &[
    ("name", "myorg/myrepo"),
    ("algorithm", "sha256"),
    ("hash", "2c26b46b68ff"),
]);

println!("{router}");
Ok::<_, Box<dyn Error>>(())

/v2
╰─ /
   ╰─ <*name>
      ╰─ /
         ├─ blobs/
         │  ├─ uploads
         │  │  ╰─ /
         │  │     ╰─ <reference>
         │  ╰─ <algorithm>
         │     ╰─ :
         │        ╰─ <hash>
         ├─ manifests/
         │  ╰─ <reference>
         ├─ referrers/
         │  ╰─ <algorithm>
         │     ╰─ :
         │        ╰─ <hash>
         ╰─ tags/list

Implementation Details

wayfind stores routes in a compressed radix trie.

When searching, each node tries its children in priority order:

1. static
2. dynamic
3. wildcard

All parameters are greedy, consuming as much of the path as possible.

Limitations

There is no backtracking across priority levels. This can result in some matches which may be unexpected.

In the following router:

/api/
├─ <version>
│  ╰─ /
│     ╰─ <*rest>
╰─ <*path>
   ╰─ /help

The path /api/docs/help would match the first route, not the second. Even though the second is arguably more specific.

Performance

wayfind is competitive with the fastest Rust routers across all benchmarks we run.

For all benchmarks, we convert any extracted parameters to strings.

All routers provide a way to return parameters as strings, but some delay the actual UTF-8 decoding until post-search.

As such, we provide 2 sets of results per benchmark:

• one with the default behaviour of the router.
• one with the parameters extracted to Vec<(&str, &str)>.

See the results at: https://codspeed.io/DuskSystems/wayfind/benchmarks

License

wayfind is licensed under the terms of both the MIT License and the Apache License (Version 2.0).

Inspirations

• poem: Initial experimentations started out as a Poem router fork
• matchit: Performance leader among pre-existing routers
• path-tree: Extensive testing and router display feature