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 such as Ruby on Rails and specifications such as 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

No backtracking happens across priority levels. Some matches can surprise you.

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 offer a way to return parameters as strings, but some delay the actual UTF-8 decoding until post-search.

As such, we offer 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://app.codspeed.io/SwornSystems/wayfind/benchmarks

License

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