Home / Rust / Data structures

path-tree - path-tree is a lightweight high performance HTTP request router for Rust

path-tree A lightweight high performance HTTP request router for Rust. Features Fast: See benchmark Micro: The src/lib.rs file is ~385 lines of code (
Information
Category: Rust / Data structures
Watchers: 4
Star: 107
Fork: 13
Last update: Dec 5, 2023
Resource links
https://github.com/viz-rs/path-tree

path-tree

A lightweight high performance HTTP request router for Rust.


Features

  • Fast: See benchmark

  • Micro: The src/lib.rs file is ~385 lines of code (Includes comments)

  • Flexible:

    • Named parameters. e.g. :name.

    • Catch-All parameters. e.g. *any, it must always be at the end of the pattern.

    • Supports multiple naming for the same path segment. e.g. /users/:id and /users/:user_id/repos.

    • Don't care about routes orders, recursive lookup, Static -> Named -> Catch-All.

Benchmark

$ cargo bench
From Travis 
path_insert/path_tree_insert

                        time:   [285.97 us 286.32 us 286.73 us]

Found 6 outliers among 50 measurements (12.00%)

  4 (8.00%) high mild

  2 (4.00%) high severe

path_insert/route_recognizer_add

                        time:   [194.49 us 194.95 us 195.49 us]

Found 4 outliers among 50 measurements (8.00%)

  1 (2.00%) high mild

  3 (6.00%) high severe

path_insert/path_table_setup

                        time:   [94.507 us 94.655 us 94.847 us]

Found 9 outliers among 50 measurements (18.00%)

  3 (6.00%) high mild

  6 (12.00%) high severe

path_insert/actix_router_path

                        time:   [14.998 ms 15.013 ms 15.029 ms]

Found 8 outliers among 50 measurements (16.00%)

  2 (4.00%) low mild

  3 (6.00%) high mild

  3 (6.00%) high severe

path_find/path_tree_find

                        time:   [375.39 us 375.73 us 376.04 us]

Found 2 outliers among 50 measurements (4.00%)

  1 (2.00%) high mild

  1 (2.00%) high severe

path_find/route_recognizer_recognize

                        time:   [1.1090 ms 1.1110 ms 1.1138 ms]

Found 4 outliers among 50 measurements (8.00%)

  2 (4.00%) high mild

  2 (4.00%) high severe

path_find/path_table_route

                        time:   [158.79 us 159.96 us 161.24 us]

Found 4 outliers among 50 measurements (8.00%)

  4 (8.00%) high mild

path_find/actix_router_recognize

                        time:   [9.1690 ms 9.1891 ms 9.2135 ms]

Found 7 outliers among 50 measurements (14.00%)

  3 (6.00%) high mild

  4 (8.00%) high severe

Path Find

Path Find

Path Insert

Path Insert

Usage

use path_tree::PathTree;

let mut tree = PathTree::<usize>::new();

tree.insert("/", 0);
tree.insert("/users", 1);
tree.insert("/users/:id", 2);
tree.insert("/users/:id/:org", 3);
tree.insert("/users/:user_id/repos", 4);
tree.insert("/users/:user_id/repos/:id", 5);
tree.insert("/users/:user_id/repos/:id/*any", 6);
tree.insert("/:username", 7);
tree.insert("/*any", 8);
tree.insert("/about", 9);
tree.insert("/about/", 10);
tree.insert("/about/us", 11);
tree.insert("/users/repos/*any", 12);

// Matched "/"
let node = tree.find("/");
assert_eq!(node.is_some(), true);
let res = node.unwrap();
assert_eq!(*res.0, 0);
assert_eq!(res.1, []); // Params

// Matched "/:username"
let node = tree.find("/username");
assert_eq!(node.is_some(), true);
let res = node.unwrap();
assert_eq!(*res.0, 7);
assert_eq!(res.1, [("username", "username")]); // Params


// Matched "/*any"
let node = tree.find("/user/s");
let res = node.unwrap();
assert_eq!(*res.0, 8);
assert_eq!(res.1, [("any", "user/s")]);

// Matched "/users/:id"
let node = tree.find("/users/fundon");
let res = node.unwrap();
assert_eq!(*res.0, 2);
assert_eq!(res.1, [("id", "fundon")]); // Params

// Matched "/users/:user_id/repos/:id"
let node = tree.find("/users/fundon/repos/trek-rs");
let res = node.unwrap();
assert_eq!(*res.0, 5);
assert_eq!(res.1, [("user_id", "fundon"), ("id", "trek-rs")]); // Params

// Matched "/users/:user_id/repos/:id/*any"
let node = tree.find("/users/fundon/repos/trek-rs/noder/issues");
let res = node.unwrap();
assert_eq!(*res.0, 6);
assert_eq!(
    res.1,
    [
        ("user_id", "fundon"),
        ("id", "trek-rs"),
        ("any", "noder/issues"),
    ]
); // Params


// Matched "/users/repos/*any"
let node = tree.find("/users/repos/");
let res = node.unwrap();
assert_eq!(*res.0, 12);
assert_eq!(res.1, []);

Examples

async-await

use hyper::service::{make_service_fn, service_fn};
use hyper::{Body, Error, Request, Response, Server, StatusCode};
use path_tree::PathTree;
use std::sync::Arc;

static NOTFOUND: &[u8] = b"Not Found";

type Params<'a> = Vec<(&'a str, &'a str)>;

type Handler = fn(Request<Body>, Params) -> Body;

fn index(_: Request<Body>, _: Params) -> Body {
    Body::from("Hello, Web!")
}

fn hello_world(_: Request<Body>, params: Params) -> Body {
    let mut s = String::new();
    s.push_str("Hello, World!\n");
    for (_, v) in params {
        s.push_str(&format!("param = {}", v));
    }
    Body::from(s)
}

fn hello_user(_: Request<Body>, params: Params) -> Body {
    let mut s = String::new();
    s.push_str("Hello, ");
    for (k, v) in params {
        s.push_str(&format!("{} = {}", k, v));
    }
    s.push_str("!");
    Body::from(s)
}

fn hello_rust(_: Request<Body>, _: Params) -> Body {
    Body::from("Hello, Rust!")
}

fn login(_req: Request<Body>, _: Params) -> Body {
    Body::from("I'm logined!")
}

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error + Send + Sync>> {
    let addr = ([127, 0, 0, 1], 3000).into();

    let mut tree = PathTree::<Handler>::new();
    tree.insert("/GET/", index);
    tree.insert("/GET/*", hello_world);
    tree.insert("/GET/hello/:name", hello_user);
    tree.insert("/GET/rust", hello_rust);
    tree.insert("/POST/login", login);

    let tree = Arc::new(tree);

    let make_service = make_service_fn(move |_| {
        let router = Arc::clone(&tree);

        async move {
            Ok::<_, Error>(service_fn(move |req| {
                let path = "/".to_owned() + req.method().as_str() + req.uri().path();

                dbg!(&path);

                let body = match router.find(&path) {
                    Some((handler, params)) => Response::new(handler(req, params)),
                    None => Response::builder()
                        .status(StatusCode::NOT_FOUND)
                        .body(NOTFOUND.into())
                        .unwrap(),
                };

                async move { Ok::<_, Error>(body) }
            }))
        }
    });

    let server = Server::bind(&addr).serve(make_service);

    println!("Listening on http://{}", addr);

    server.await?;

    Ok(())
}

normal

extern crate futures;
extern crate hyper;
extern crate path_tree;

use futures::Future;
use hyper::server::Server;
use hyper::service::service_fn_ok;
use hyper::{Body, Request, Response, StatusCode};
use path_tree::PathTree;
use std::sync::Arc;

type Params<'a> = Vec<(&'a str, &'a str)>;

type Handler = fn(Request<Body>, Params) -> Body;

fn index(_: Request<Body>, _: Params) -> Body {
    Body::from("Hello, Web!")
}

fn hello_world(_: Request<Body>, params: Params) -> Body {
    let mut s = String::new();
    s.push_str("Hello, World!\n");
    for (_, v) in params {
        s.push_str(&format!("param = {}", v));
    }
    Body::from(s)
}

fn hello_user(_: Request<Body>, params: Params) -> Body {
    let mut s = String::new();
    s.push_str("Hello, ");
    for (k, v) in params {
        s.push_str(&format!("{} = {}", k, v));
    }
    s.push_str("!");
    Body::from(s)
}

fn hello_rust(_: Request<Body>, _: Params) -> Body {
    Body::from("Hello, Rust!")
}

fn login(_req: Request<Body>, _: Params) -> Body {
    Body::from("I'm logined!")
}

fn main() {
    let addr = ([127, 0, 0, 1], 3000).into();

    let mut tree = PathTree::<Handler>::new();
    tree.insert("/GET/", index);
    tree.insert("/GET/*", hello_world);
    tree.insert("/GET/hello/:name", hello_user);
    tree.insert("/GET/rust", hello_rust);
    tree.insert("/POST/login", login);

    let tree = Arc::new(tree);

    let routing = move || {
        let router = Arc::clone(&tree);

        service_fn_ok(move |req| {
            let path = "/".to_owned() + req.method().as_str() + req.uri().path();

            dbg!(&path);

            match router.find(&path) {
                Some((handler, params)) => Response::new(handler(req, params)),
                None => Response::builder()
                    .status(StatusCode::NOT_FOUND)
                    .body(Body::from("Not Found"))
                    .unwrap(),
            }
        })
    };

    let server = Server::bind(&addr)
        .serve(routing)
        .map_err(|e| eprintln!("server error: {}", e));

    hyper::rt::run(server);
}

Acknowledgements

It is inspired by the:

License

This project is licensed under either of

at your option.

7 Open More issues
Closed

Redesign

Named parameters

Named parameters are defined by prefixing a colon to the parameter name (:name), pattern is ([^\/#\?]+).

/heros/:name

path | match | params ------------------- | ------ | ------- /heros/io | YES | name=io /heros/morphling | YES | name=morphling /heros/123 | YES | name=123 /heros/io/123 | NO | /heros/ | NO |

/foo `/foo/bar`
/foo/bar `/foo/bar`
/:name `/rust`
/:name.:ext `/users.json`
/:year.:month.:day/:name.:ext `/2022.12.12/users.json`
/:controller::action   `/users:run`
/*any `/any`
/prefix:param::postfix
opened Jun 18, 2022 by fundon 13
Closed

Remove lifetime

A mentioned in #18 the added lifetime would limit use of the API as well as cause issue with PyO3 bindings. This removes it using Vecs and to_vecs.

I do plan on using this commit as the basis for my optimization experiments which may be included depending on if this is merged or not.

Benchmark (mimalloc):

matchit path-tree w/o lifetime
insert 59µs 73µs 84µs
find 45µs 40µs 40µs

Benchmark (Windows' allocator):

matchit path-tree w/o lifetime
insert 109µs 128µs 158µs
find 31µs 40µs 39µs
opened Sep 22, 2022 by Txuritan 11
Closed

feat: handle empty paths

I needed this so that I can compose routers, something like:

Router(
  {
    "/users": Router(
      {
        "": users_endpoint,
        "/:name": user_endpoint,
       }
    )
)

Basically the "value" can be an endpoint or another router, but currently the router assumes/forces the path to start with "/" which in this example means it's impossible to match "/users".

I did this in a TDD style because I'm unfamiliar with the codebase and barely know Rust: I wrote the test and then hacked until I got it to work. I'm still pretty new to rust so please feel free to rip my work apart and apologies if this is missing some obvious edge case that I didn't pick up from the code.

opened Jul 14, 2022 by adriangb 8
Closed

chore: allow empty str

#19

@adriangb try this branch

opened Sep 24, 2022 by fundon 6
Closed

Python wrapper

Just FYI, I thought this was cool and made a Python wrapper: https://pypi.org/project/routrie/

opened Jan 11, 2022 by adriangb 6
Closed

implement Clone trait for PathTree

null

opened Feb 16, 2023 by kotlin2018 5
Open

Port to Node, Deno or Zig

null

opened Nov 5, 2023 by fundon 0
Open

Regexp

https://github.com/devongovett/glob-match

opened Jan 16, 2023 by fundon 0
Open

mustermann

https://github.com/sinatra/mustermann

opened Nov 24, 2022 by fundon 0
Open

Remove element from tree, by id

Would it be possible to remove a path from the tree, by id?

Looking through the code, it looks like it might be possible, but I'm not exactly sure how I'd do it.

opened Oct 13, 2022 by jeromegn 1
Open

WASM

null

opened Sep 28, 2022 by fundon 0
Open

Add new node kinds

  • Regex: supports regex on parameter
  • ~Root?: allow '' empty str at top of the tree, replace /~
opened Sep 26, 2022 by fundon 1

v0.7.2(Jul 31, 2023)

v0.7.1(Oct 29, 2022)

Changes

  • remove format! for debug

v0.7.0(Oct 3, 2022)

Breaking Changes

  • find will return a tuple Option<(&T, Path)>

v0.6.0(Sep 27, 2022)

no_std support

v0.5.2(Sep 26, 2022)

  • Supports Parameters Iterator
  • Supports update node value

v0.5.1(Sep 23, 2022)

  • Remove lifetime

  • Inserts then returning node id

Contents

    steambap high performance router for Koa
    fasthttp Router is a lightweight high performance HTTP request router
    julienschmidt A high performance HTTP request router that scales well
    beego A high performance and powerful trie based url path router for Go.
    vuejs vue-router - The official router for Vue.js.
    vuejs 🚦 The official router for Vue.js.
    AwesomeDevin Static file serving middleware with router,wrapper for koa-send.
    egoist A router that works in Node.js, browser and Deno.
    mufancom A type-safe MobX router with parallel routing support.
    40818419 vue-router-sitemap - Generate sitemap.xml by vue-router configuration
    dimfeld High-speed, flexible tree-based HTTP router for Go.
    donutloop mux is a lightweight HTTP request router
    claygod Bxog is a simple and fast HTTP router for Go (HTTP request multiplexer).
    jaraco Object-oriented file system path manipulation
    szxp Lightweight HTTP request multiplexer (router) for Golang
    cloudnativelabs Kube-router, a turnkey solution for Kubernetes networking.
    David-Desmaisons Vue.D3.tree D3.jsVue.D3.tree - A Tree View based on D3.js
    lanjingling0510 🐰 🏀 look a demo , URL:
    ios-utils Navigate anywhere in just one line.
    taion React Router scroll management
    choojs 🛤 - Small frontend router
    Share this repo

    Related Repos


    Data structures
    265
    A minimal `syn` syntax tree pretty-printer
    dtolnay prettyplease::unparse A minimal syn syntax tree pretty-printer. Overview This is a pretty-printer to turn a syn syntax tree into a String of well-form
     
    Data structures
    4
    A memory efficient syntax tree for language developers
    udoprog syntree A memory efficient syntax tree. This crate provides a tree structure which always is contiguously stored and manipulated in memory. It provide
     
    Data structures
    8
    Rust library providing fast language model queries in compressed space
    kampersanda tongrams-rs: Tons of N-grams in Rust This is a Rust port of tongrams to index and query large language models in compressed space, in which the data s
     
    Data structures
    5
    Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface
    skmendez tree-sitter-traversal Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface. Using cursors, iteration over the tree c
     
    Data structures
    3
    A tiny rusty Xmas tree without bells and whistles
    lmammino xmas A tiny rusty Xmas tree without bells and whistles Run Just clone this repo and run: cargo run (Requires to have Rust installed) Contributing Ever
     
    Data structures
    33
    A LED Christmas Tree controlled by Rust. Contribute your own renderers!
    AngelOnFira Rusty Christmas Tree This is code that draws on the LED Christmas Tree made by @aidancrowther. You can see his 3D design files and Pi Pico setup code
     
    Data structures
    3
    A syntax highlighter for Node powered by Tree Sitter. Written in Rust.
    devongovett tree-sitter-highlight A syntax highlighter for Node.js powered by Tree Sitter. Usage The following will output HTML: const treeSitter = require('tree-
     
    Data structures
    229
    Tree command, improved.
    dduan tre A modern alternative to the tree command that: lists directory structure in a tree-like diagram, like the classics. skips ignored files in git rep
     
    Data structures
    12
    Serialize & deserialize device tree binary using serde
    luojia65 serde_device_tree Use serde framework to deserialize Device Tree Blob binary files; no_std compatible. Use this library Run example: cargo run --examp
     
    Data structures
    10
    StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL
    AFLplusplus StdFuzzer StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL Building Build with $ cargo build --release Compiling a
     
    Data structures
    9
    Rasterization using compute shaders
    pudnax gpu_compute_rasterizer This is a basic implementation of a rasterizer using compute shaders and wgpu. Based on: https://github.com/OmarShehata/webgpu-
     
    Data structures
    3
    A "cursed" container with opaque keys, usable as a static variable
    u1f408 cursedcontainer Please, for the love of all things good in the world, do not use this crate unless you've read the code thoroughly and understand the
     
    Data structures
    3
    Voluntarily contributed solutions for the first practical exercise for the Compilerbau lec...
    Yandrik Solutions for the first practical exercise Compilerbau lecture WiSe 2021/2022 - Ulm University Contributing Want to add your solution? Great! Just add
     
    Data structures
    12
    Common data structures and algorithms for competitive programming in Rust
    utilForever algorithm-rs algorithm-rs is common data structures and algorithms for competitive programming in Rust. Contents TBA How To Contribute Contributions a
     
    Data structures
    1.4k
    Rust implementations of algorithms and data structures useful for bioinformatics.
    rust-bio This library provides implementations of many algorithms and data structures that are useful for bioinformatics. All provided implementations are rigorously tested via continuous integration.