dream - v2.3.2

dream/router/trie

Radix Trie - Fast route matching data structure

Provides O(path depth) route lookup instead of O(number of routes) linear search. This is the core data structure used by Dream’s router for efficient route matching.

Performance Characteristics

How It Works

The trie organizes routes as a tree where each level represents a path segment. Nodes are prioritized in this order:

  1. Literal matches (exact string match)
  2. Parameter matches (:id)
  3. Single wildcards (*)
  4. Extension patterns (*.jpg)
  5. Multi-wildcards (**)

This ensures the most specific route always wins when multiple routes could match.

Example

Routes: /users/:id, /users/new, /files/**path

Tree structure:

root
  └─ users
     ├─ new (literal - highest priority)
     └─ :id (param - lower priority)
  └─ files
     └─ **path (multi-wildcard - lowest priority)

Path /users/new matches the literal route, not :id.

Types

Match

</>

Result of a successful route lookup

Contains the matched route and any extracted path parameters.

pub type Match(route) {
  Match(route: route, params: List(#(String, String)))
}

Constructors 

  • Match(route: route, params: List(#(String, String)))

    Arguments

    route

    The route that matched the request

    params

    Extracted parameters from the path as (name, value) tuples

RadixTrie

opaque </>

Radix trie for fast route lookup

The trie is the main data structure holding all routes. Routes are organized by path segments for efficient O(path depth) lookup.

pub opaque type RadixTrie(route)

Segment

</>

Segment types for route patterns

Each segment type has different matching behavior and priority:

  • Literal: Exact string match, highest priority
  • Param: Named parameter, captures one segment
  • SingleWildcard: Matches one segment, optionally named
  • MultiWildcard: Matches zero or more segments, optionally named
  • ExtensionPattern: Matches filenames with specific extensions
  • LiteralExtension: Matches a specific base name with allowed extensions
pub type Segment {
  Literal(String)
  Param(name: String)
  SingleWildcard(name: option.Option(String))
  MultiWildcard(name: option.Option(String))
  ExtensionPattern(extensions: List(String))
  LiteralExtension(base: String, extensions: List(String))
}

Constructors 

  • Literal(String)

    Literal segment requiring exact match Example: "users" in /users/:id

  • Param(name: String)

    Named parameter capturing one segment Example: "id" in /users/:id

  • SingleWildcard(name: option.Option(String))

    Single wildcard matching exactly one segment Example: * or *file in /images/*file

  • MultiWildcard(name: option.Option(String))

    Multi-segment wildcard matching zero or more segments Example: ** or **path in /files/**path

  • ExtensionPattern(extensions: List(String))

    Extension pattern matching specific file extensions (wildcard) Example: ["jpg", "png"] in /images/*.{jpg,png}

  • LiteralExtension(base: String, extensions: List(String))

    Literal with specific extensions (not wildcard) Example: products with ["json", "xml"] for /products.{json,xml} Matches products.json or products.xml but not other.json

TrieNode

opaque </>

A node in the radix trie

Each node can store routes for different HTTP methods and has children for different segment types. Children are organized by priority to ensure correct matching order.

pub opaque type TrieNode(route)

Values

insert

</> 
pub fn insert(
  trie: RadixTrie(route),
  method: String,
  segments: List(Segment),
  route: route,
) -> RadixTrie(route)

Insert a route into the trie

Adds a route at the path specified by the segments. If a route already exists for the same method and path, it is replaced.

Parameters

  • trie: The trie to insert into
  • method: HTTP method as string (e.g., “GET”, “POST”)
  • segments: Path segments from pattern parser
  • route: The route handler to store

Example

let trie = new()
|> insert("GET", [Literal("users"), Param("id")], handler)
|> insert("POST", [Literal("users")], create_handler)

lookup

</> 
pub fn lookup(
  trie: RadixTrie(route),
  method: String,
  path_segments: List(String),
) -> option.Option(Match(route))

Look up a route in the trie

Searches for a route matching the given HTTP method and path segments. Returns the matched route and extracted parameters, or None if no match.

Lookup is O(path depth) - independent of the total number of routes in the trie.

Parameters

  • trie: The trie to search
  • method: HTTP method as string (e.g., “GET”, “POST”)
  • path_segments: Path split into segments (e.g., [“users”, “123”])

Returns

  • Some(Match): Contains the matched route and extracted parameters
  • None: No route matched the method and path

Example

let result = lookup(trie, "GET", ["users", "123"])
case result {
  Some(Match(route, params)) -> {
    // params = [#("id", "123")]
    // route is the handler
  }
  None -> // No matching route
}

new

</> 
pub fn new() -> RadixTrie(route)

Create a new empty radix trie

Returns a trie with no routes. Use insert() to add routes.

Example

let trie = new()
|> insert("GET", [Literal("users")], user_handler)
✨ Search Document