Creating URL Routing: Episode 1

Overview

Previously, I created a very basic routing system in React (cf. Creating a custom router using React and History API), but I decided to challenge myself to create a more robust routing system. The motivation came from working with Golang recently.

In Golang, the standard library allows for lightweight application implementation, but the routing functionality is somewhat underpowered, often requiring reliance on external libraries. This inspired me to learn how to create my own routing system, which could expand my capabilities not only in Golang but also in other languages.

What is URL Routing?

URL routing determines the process to execute based on the requested URL. It also handles path parameters and query parameters as needed during execution.

URL Routing Implementation Patterns

Broadly speaking, there are two patterns:

Using regular expressions for URL matching
Using tree structures for string searching

Although routing may not significantly impact application execution speed, optimizing memory usage and computational complexity with efficient algorithms is always preferable, regardless of the programming language.

For this implementation, I chose the tree structure pattern. While I haven't measured performance, I believe tree structure algorithms are computationally more efficient than regular expressions. Many libraries are implemented using tree structures.

What is a Tree Structure?

A tree structure is a type of data structure defined in the mathematical field of graph theory. A tree in graph theory consists of multiple nodes (also called vertices) and edges.

There are various types of tree structures depending on node properties and tree height, but we'll omit those details here.

Examples of Tree Structures

Family trees
File systems
Domain names
- cf. https://www.nic.ad.jp/ja/dom/system.html
Syntax trees
- Used in compilers
DOM trees
Hierarchical tags or category structures

Creating URL Routing

What should be treated as a tree structure? Naturally, the list of route definitions will be treated as a tree structure.

The implementation process can be summarized as follows: given route definitions and the current URL (path) as input, generate a tree structure from the route definitions, search the tree structure using the current URL (path) as the target, and return the matched data.

When working with tree structures, operations like adding or deleting nodes are sometimes implemented. However, for URL routing, these operations are unnecessary for now.

Defining the Data Structure

First, define the DSL (Domain-Specific Language) for routing. Many libraries provide simple DSLs, but this time, I’ll define a slightly more complex DSL with multiple levels.

Instead of generating a tree structure from route definitions, I decided to define the route definitions directly as a tree structure. This approach reduces unnecessary algorithms, potentially improving performance. While this DSL may seem straightforward, I suspect there are reasons why common routing libraries don’t use this format.

The terminal nodes (leaves) of the tree structure correspond to HTTP methods.

Prepare a list of HTTP methods separately. In Golang, these are predefined in net/http, which is convenient. For this example, I’ll use PHP.

Implementation

Implement two functions: one to process the current URL (path) into an array for easier tree traversal, and another to compare the route definitions with the target route array and return the matched path data. Query parameters are not considered in this implementation.

To ensure portability across languages, I’ll minimize the use of built-in functions.

This concludes Episode 1 as the implementation is still in progress.

Thoughts

Starting directly with complex structures like Patricia trees or other advanced trees can be overwhelming. While I’ve looked at various implementations for reference, understanding each one is quite challenging. For now, I’ve focused on grasping the algorithm’s concept and working through it step by step. However, lacking mathematical knowledge can be tough.

Although the implementation is incomplete, I feel like I’m starting to see the goal. That said, I’m not confident this will evolve into a base suitable for practical use.

Postscript

I presented this topic at the Makuake LT Party (an internal LT event).

speaker-deck - Creating URL Routing: Episode 1