Tonics Router Library (Introduction & Inspiration Behind The Library)

In this guide, I will introduce and write about the inspiration behind the Tonics Router Library which is the router behind Tonics, without any further ado, let's get into it...

The Tonics Router Library is a self-discovered Trie-based PHP Router System For Tonics Projects, self-discovered because I didn't know I was using the trie algorithm when I came up with the idea, later discovering someone has done something similar gave me some kinda cool feeling if you get me.

A quick explanation of how it works before I go deeper:

Unlike traditional PHP Routers, the Tonics Router uses a tree data structure where every path is hierarchically organized making it faster for finding both static and dynamic URLs.

Inspiration Behind The Idea

When I was learning how PHP frameworks work behind the scene, the way I matched a URL to a controller class is by splitting the request URL into an array, do some pre-processing, and then match to the Controller.  I wrote about this in my Building a Tiny PHP Framework From Scratch on Devsrealm Blog (note that, that approach is stupid so it's only a reference at this point). 

But I keep thinking about a better way to do routing without using the above method or resorting to using regex or even if I'll use regex, it should be minimal, so I said if I could split a URL into an array, is there a better way I could arrange them hierarchically such that the retrieval of a route node would be easier, let's say you are looking for this route node: /home/in/in, common sense tells me, to get to that path, I would need to go into "home", then "in", and then "in" (which can also be dynamic), but to do that I'll need to build some kind of a tree that can hold node and their connecting siblings.

Having gotten a little information on what I'll be doing, I started brainstorming, and came up with the following in the below image:

Hmm 🤔, I think this is resembling a tree, I kept drawing nodes, connecting them, and drafting state machines for the overall tree generator:

The Solution

I won't go into too much detail, I would only give an explanation of how the RouteTreeGeneratorState works:

Note: Each path would go over the state machine, so, if we have /home/in/in, each of [/], [home], [in], and [in] would have to go over the state machine one at a time.

TonicsInitialStateHandler

• If the first character is a solidus (/), then we add it to the routePath array, and finally, insert the node while also setting it as a static parameter
• If the first character is an ASCII or ASCII Digit, we reconsume in the TonicsStaticParameterStateHandler
• If the first character is a column (:), we reconsume in the TonicsRequiredParamterStateHandler, meaning this is a dynamic path
• Else: We throw a run time exception

TonicsStaticParameterStateHandler

• We store the current path in the routePath array and insert the node while setting the static parameter to true

TonicsRequiredParameterStateHandler

• We store the current path in the routePath array and insert the node while storing the requiredParamater to true and the isStatic property to false

Node Insertion

Before inserting the node, we first switch the routeTreeGeneratorState to TonicsInitialStateHandler, and then insertNodeInAppropriatePosition which is gonna return the result node, we check if that is not null, and if it isn't null, we set it as the lastAddedRouteNode while also returning it.

Insert Node In Appropriate Position

• Before loop, create a new $node variable and set it to null
• For each route path, we findAppropriatePositionToInsertOrUpdateNode
• If the appropriate position to insert the node is found, we check if it is a requiredParameter, if so, then the path is also required and it should be on the same tree level, so, we update its settings (controller method, route alias, name, etc), lastly set the $node variable to $findNode
• If the appropriate position can't be found, create a new RouteNode object, add the node to root, set the parentNode to root, and lastly, update $root to $node

At the end of the loop, return the $node.

The above is just a glimpse of the solution, but you can go over the final solution in the Tonics Router Repo

Conclusion

At the end of the router project, I thought of searching for the term tree-based router since it really does resemble a tree data structure, that is how I knew it is called a trie-based router, the way the insertion and node finding works is similar to the trie algorithm, but I may be wrong, so corrections are welcome.

The crazy thing is, I discovered other algorithms when working on other libraries for the Tonics project, I don't know their name yet, but hopefully, when I post it, someone can tell me the name.

Again, you can go over the router repo to check out the full solution, which you can incorporate into your own project if you want to, the project doesn't have any license, so, you are free to use whatever license you want, hey, you can even make it open source or closed source, I don't care, if adding a license is that important to you, reach out, and I can add whatever license you want specifically if that would make you happy.