Swift Code Craft: TrieRouter from Vapor

👍

· Feb 23, 2025 · 7 mins read

Welcome to the Swift Code Craft series. This collection explores ingenious Swift solutions to practical problems, highlighting elegant implementations that balance performance with simplicity. Each piece examines how Swift’s features can be leveraged to create code that’s both powerful and maintainable. Join us as we uncover valuable insights and techniques from the Swift ecosystem that you can apply to your own projects.

Vapor has been one of the most popular Web Server frameworks written in Swift. At its core, like any other web frameworks, lies a critical component: the router. Vapor’s implementation, the TrieRouter<Output>, represents an elegant combination of efficiency and simplicity.

Understanding the Problem

Web routing is the process of determining how a web server responds to different URLs (routes) requested by a client. It maps incoming HTTP requests (like GET /home or POST /login) to specific handler functions in the server’s code that generate a response.

A key challenge in web routing is maintaining scalability and clarity as the number of routes grows. It becomes harder to manage nested routes, enforce consistent patterns, and avoid route conflicts or duplication — especially in large applications.

Performance: Considering the need of handling numerous of requests, routes must be matched quickly, even when there are hundreds or thousands of routes.
Parameter extraction: Dynamic path components must be efficiently captured, which is very common in Restful api design patterns, where certain parameters are part of the URL path.

The Trie data structure

Unlike many other web server frameworks, which are using hash table, dictionary search or regex-based solutions, the Vapor uses a trie data structure, a specialised tree where each node represents a path component.

For example, for the list of url paths below:

GET /api/users  
POST /api/users  
GET /api/users/:id  
PUT /api/users/:id  
DELETE /api/users/:id  
GET /api/products  
POST /api/products  
GET /api/products/:id  
PATCH /api/products/:id  
DELETE /api/products/:id  
GET /api/orders  
POST /api/orders  
GET /api/orders/:id  
PUT /api/orders/:id  
DELETE /api/orders/:id  
GET /api/categories  
POST /api/categories  
GET /api/categories/:id/items  
GET /api/items/:id/reviews  
POST /api/items/:id/reviews

Vapor will generate a Trie tree like below.

api  
├── GET  
│   ├── users  
│   ├── users  
│   │   └── parameter("id")  
│   ├── products  
│   ├── products  
│   │   └── parameter("id")  
│   ├── orders  
│   ├── orders  
│   │   └── parameter("id")  
│   ├── categories  
│   └── categories  
│       └── parameter("id")  
│           └── items  
├── POST  
│   ├── users  
│   ├── products  
│   ├── orders  
│   ├── categories  
│   └── items  
│       └── parameter("id")  
│           └── reviews  
├── PUT  
│   ├── users  
│   │   └── parameter("id")  
│   └── orders  
│       └── parameter("id")  
├── DELETE  
│   ├── users  
│   │   └── parameter("id")  
│   ├── products  
│   │   └── parameter("id")  
│   └── orders  
│       └── parameter("id")  
└── PATCH  
    └── products  
        └── parameter("id")

Basically, firstly it groups APIs based on the http methods, then the path components. For the routing process, it just follows the tree structure to match the request url path, then call the responder method it stored in the node.

A trie offers O(k) lookup complexity, where k is the path depth (number of components). This means performance remains consistent regardless of how many routes we have in the application.

The Implementation

Let’s explore the core components of Vapor’s TrieRouter:

// Extracted from https://github.com/vapor/routing-kit/blob/main/Sources/RoutingKit/TrieRouter.swift  
public final class TrieRouter<Output>: Router, CustomStringConvertible {  
...  
    public init(_ type: Output.Type = Output.self, options: Set<ConfigurationOption> = []) {  
        self.root = Node()  
        self.options = options  
        self.logger = .init(label: "codes.vapor.routingkit")  
    }  
...  
}

The TrieRouter was defined as a Genetic class to make the its nodes be able to hold different types of values. In Vapor, the Output is a type that containsResponder that responds to the URL path that the node matches.

The register(_ output: Output, at path: [PathComponent]) method is responsible to register a path into router and build the Trie tree. The magic of creating and organising node into the right position happens in the Node structure.

The route(path: [String], parameters: inout Parameters) -> Output? method is responsible for retrieving the Responder from the Tri tree, which is a standard Tri tree search algorithm implementation and done using this loop search: for (index, slice) in path.enumerated() {...}.

The Node Structure

Each node in the trie represents a path component and contains an output value depending on the registration:

// Extracted from https://github.com/vapor/routing-kit/blob/main/Sources/RoutingKit/TrieRouter.swift  
    final class Node: CustomStringConvertible {  
...  
        init(output: Output? = nil) {  
            self.output = output  
            self.constants = [String: Node]()  
        }  
          
        func buildOrFetchChild(for component: PathComponent, options: Set<ConfigurationOption>) -> Node {  
            ...  
        }  
    }

The magic of building Trie is inside method func buildOrFetchChild(for component: PathComponent, options: Set<ConfigurationOption>) -> Node . When registering a url path, this method is responsible to add this into the proper position of the Trie tree.

Path Components

The PathComponent is another amazing type that generalise the parts of the url path.

// Extracted from https://github.com/vapor/routing-kit/blob/main/Sources/RoutingKit/TrieRouter.swift  
public enum PathComponent: ExpressibleByStringInterpolation, CustomStringConvertible, Sendable, Hashable {  
    /// A normal, constant path component.  
    case constant(String)  
  
    /// A dynamic parameter component.  
    ///  
    /// The supplied identifier will be used to fetch the associated  
    /// value from `Parameters`.  
    ///  
    /// Represented as `:` followed by the identifier.  
    case parameter(String)  
      
    /// A dynamic parameter component with discarded value.  
    ///  
    /// Represented as `*`  
    case anything  
      
    /// A fallback component that will match one *or more* dynamic  
    /// parameter components with discarded values.  
    ///  
    /// Catch alls have the lowest precedence, and will only be matched  
    /// if no more specific path components are found.  
    ///  
    /// The matched subpath will be stored into `Parameters.catchall`.  
    ///  
    /// Represented as `**`  
    case catchall  
...  
}

It is an enum type and this elegant enum encapsulates the various types of path components Vapor needs to handle:

Constants like “users” or “products”
Parameters like values in the url path
Anything and Catchalls for wildcard routes

How Vapor Puts everything together

Registration

There are a few ways to register routs in Vapor, some of which are the following:

public func get<Response>(  
        _ path: PathComponent...,  
        use closure: @Sendable @escaping (Request) async throws -> Response  
    ) -> Route  
    where Response: AsyncResponseEncodable  
  
public func get<Response>(  
        _ path: [PathComponent],  
        use closure: @Sendable @escaping (Request) async throws -> Response  
    ) -> Route  
    where Response: AsyncResponseEncodable  
...

It’s worth mentioning that Variadic Parameters usage in the first method, which allows flexible usage like below:

app.get("api", "users") { req in  
    ...  
}  
app.get("api", "users", ":id") { req in  
    ...  
}

Routing

When a request arrives, Vapor splits the path like below and extracts the path components from the URL and feeds them to the public func route(path: [String], parameters: inout Parameters) -> Output? method of TrieRouter and get the Responder to process the request.

let pathComponents = request.url.path.split(separator: "/").map(String.init)

The Beauty in Simplicity

What makes TrieRouter elegant isn’t just its efficiency, but its simplicity. The entire implementation is remarkably concise, yet it handles the complex requirements of web routing with grace.

The design follows several Swift best practices:

Use of generics (Output) for flexibility
Clear separation of concerns
Strong typing with enums for path components
Efficient algorithms under a clean API

Several valuable lessons can be extracted from studying TrieRouter:

Choose the right data structure: The trie structure perfectly matches the hierarchical nature of URL paths
Use generics strategically: The Output type parameter allows the router to be used for different purposes
Balance flexibility and performance: The implementation doesn’t sacrifice speed for features
Keep the API simple: Despite its complex internals, using the router is straightforward
Separate concerns cleanly: Path matching, parameter extraction, and response handling are distinct

Beyond Vapor: When to Use a Trie

The trie approach isn’t just valuable for web routing. Consider this data structure when:

Need to match hierarchical paths or prefixes
Lookup performance is critical
Memory efficiency matters for a large number of entries

Examples include:

File system path resolution
Auto-completion systems
IP routing tables
Permission systems

Conclusion

Vapor’s TrieRouter exemplifies Swift code craft at its finest – solving a complex problem with an elegant, efficient implementation. Its design balances performance needs with API simplicity, creating a component that works reliably at scale while remaining easy to understand and maintain.

Coding life