DEV Community

Cover image for Creating URL Routing Episode 1
Kenta Takeuchi
Kenta Takeuchi

Posted on • Originally published at bmf-tech.com

Creating URL Routing Episode 1

#http #urlrouting #treestructure #router

This article was originally published on bmf-tech.com.

Creating URL Routing Episode 1

Overview

Previously, I created a very basic routing system using React (cf. Creating a Custom Router with React and History API), but I wanted to challenge myself to create a more proper routing system. The trigger for this was my recent experience with Golang. It seems that by utilizing the standard library in Golang, applications can be implemented quite thinly, but the routing aspect often lacks power in the standard library, leading to a reliance on external libraries. Because of this, I felt that being able to create my own routing system would expand my capabilities in Golang and beyond, so I decided to take the plunge.

What Does URL Routing Do?

It determines what processing should be executed in response to a requested URL. If necessary, it allows handling of path parameters and query parameters during the execution of the processing.

Implementation Patterns for URL Routing

There are roughly two patterns:

  • A pattern that matches URLs using regular expressions.
  • A pattern that uses a tree structure for string searching.

While the impact of routing on application execution speed may not be significant, it is always better to be as fast as possible. Regardless of the language, it should be implemented with optimized algorithms for memory usage and computational complexity.

This time, I will choose the pattern implemented with a tree structure. Although I haven't measured performance, I feel that using a tree structure algorithm is likely to be more efficient than regular expressions, so I will go with that. In fact, there are many libraries implemented with tree structures.

What is a Tree Structure?

A data structure that has a tree structure defined in the field of graph theory in mathematics. A tree defined in graph theory consists of multiple points (nodes or vertices) and multiple edges.

   ○ ・・・Root
 / | ・・・Edge
◯  ◯ ・・・Node
    \
  　  ◯
       \
    　   ○ ・・・Leaf
Enter fullscreen mode Exit fullscreen mode

There are various types of tree structures depending on the properties of the nodes and the height of the tree, but I will omit those details here.

Examples of Tree Structures

Creating URL Routing

What will we treat as a tree structure? Of course, we will treat the list of route definitions as a tree structure.

To roughly explain the implementation flow, when given the route definitions and the current URL (path) as input, we will generate a tree structure from the route definitions, explore the tree structure targeting the current URL (path), and return the matched data.

When handling the tree structure, there may be cases where we implement processes such as adding or deleting nodes, but for URL routing, we will not implement those for now.

Deciding on the Data Structure

We will first decide on the DSL for the routing definitions. Many libraries provide a simple DSL, but this time we will define a slightly complex DSL with multiple layers.

$routes = [
    '/' => [
        'GET' => 'HomeController@get',
    ],
    '/users' => [
        '/' => [
            'GET' => 'UserController@get',
        ],
        '/:user_id' => [
            '/' => [
                'GET' => 'UserController@get',
                'POST' => 'UserController@post',
            ],
            '/events' =>  [
                '/' => [
                    'GET' => 'EventController@get',
                ],
                '/:id' => [
                    'GET' => 'EventController@get',
                    'POST' => 'EventController@post',
                ],
            ]
        ],
        '/support' => [
            '/' => [
                'GET' => 'SupportController@get',
            ],
        ]
    ],
];
Enter fullscreen mode Exit fullscreen mode

I mentioned earlier that we would generate a tree structure from the route definitions, but we will define the route definitions in a way that they are already structured as a tree. The reason for this approach is simply that writing an algorithm to generate a tree structure seems cumbersome, but conversely, it might reduce unnecessary algorithms and improve performance. I believe the route definitions are not particularly difficult to understand, but I think there must be a reason why common routing libraries do not adopt this structure.

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

In addition to the tree structure, we will prepare a list of HTTP methods. In Golang, they are already defined in net/http, which is convenient. This time, we will do it in PHP...

$methods = [
    'GET',
    'POST',
    // more...
];
Enter fullscreen mode Exit fullscreen mode

Implementation

We will implement two functions: one to process the current URL (path) into an array for easier exploration of the tree structure, and another that takes the array and the route definitions array as arguments to return the matched path data. Note that we are not particularly considering query parameters this time.

As an implementation policy, we will avoid using built-in functions as much as possible to consider portability to other languages.

function createCurrentPathArray($routes) {
    $currentPath = '/users/1'; // Current path

    $currentPathLength = strlen($currentPath);

    $currentPathArray = [];

    for ($i=0; $i < $currentPathLength; $i++) {
        if ($currentPathLength == 1) {
            $currentPathArray[] = '/';
        } else {
            if ($currentPath{$i} == '/') {
                $currentPathArray[] = '/';
                $target = count($currentPathArray) - 1;
            } else {
                $currentPathArray[$target] .= $currentPath{$i};
            }
        }
    }

    return $currentPathArray;
}

// Exploration
// Compare the route definitions and the target route array to return the corresponding data.
// End exploration when reaching a leaf.
function urlMatch($routes, $currentPathArray) {
    // TODO Implementing...
}

$currentPathArray = createCurrentPathArray($routes);
$result = urlMatch($routes, $currentPathArray);

var_dump($result); // Should return the matched path data...
Enter fullscreen mode Exit fullscreen mode

As this is still a work in progress, Episode 1 comes to a close here.

Thoughts

If you try to start with Patricia trees or other complex structures from the beginning, you might get burned badly. I looked at various implementations that might be helpful, but understanding each one is quite hard, so I started by grasping the image of the algorithm and working with my hands. However, it can be tough if you lack mathematical background. Although it is still in progress, I feel like I can see the goal somewhat. However, I am not confident that I can bring it to a level that can be used in actual operations.

Postscript

I gave a talk at the Makuake LT Party (internal LT competition).

speaker-deck - Creating URL Routing Episode 1

References

Top comments (0)