Ex. Implementing Dynamic Routing

When we're building a server application, dynamic routing is an essential feature for creating flexible and scalable applications. To fully grasp its significance and how we can enhance our router to support dynamic routes like /users/:id, let's delve into the concept of dynamic routing.

Why Dynamic Routing?

At its core, dynamic routing refers to the ability of a web application (not just server) to handle requests to URLs that are not predetermined but rather, are defined by patterns. It allows developers to create routes that can match a range of URL structures, often using parameters. For instance, a URL like /users/:user_id can handle requests for any user ID, where :user_id is a variable part of the URL.

Flexibility

Dynamic routing introduces a level of flexibility that static routing cannot match. As applications grow and become more complex, new routes often need to be added. With dynamic routing, you can handle a vast number of routes with just a few route patterns, making the application more scalable and easier to maintain. For example, imagine having to define a route for every kind of asset your website serves.

You may do something like this

// images
app.get("/static/imgs/img1.png", img_handler);
app.get("/static/imgs/img2.png", img_handler);
app.get("/static/imgs/img3.png", img_handler);
app.get("/static/imgs/img4.png", img_handler);

// javascript
app.get("/static/js/main.js", script_handler);
app.get("/static/js/third_party.js", script_handler);

/** And so on**/

This is quite tedious, and you cannot expect an application like this to scale. What if we had a dynamic route to serve all the assets?

app.get("/static/img/:image_file_name", img_handler);
app.get("/static/js/:javascript_file_name", img_handler);

This is somewhat better than the previous.

Better User Experience

Dynamic routes allow for creating more personalized user experiences. For example, in a blog application, a dynamic route like /posts/:postId can display a specific post based on the ID in the URL. This approach makes it straightforward to link to specific content, improving the navigability and user engagement.

Better Developer Experience

By using dynamic routes, developers of our framework can avoid the tedium of defining every possible URL path in their application. This not only saves time but also reduces the risk of errors. A single dynamic route can replace dozens, if not hundreds, of static routes, streamlining the development process.

Better SEO

Dynamic routing can also contribute to better Search Engine Optimization (SEO). With the ability to generate clean and meaningful URLs (e.g., /game/dota2 instead of /game?uid=dota2), dynamic routes make URLs more understandable to both users and search engines, potentially improving search rankings.

Anatomy of a dynamic route

A dynamic route follows a structure where certain parts of the URL path are variable, known as dynamic segments.

/[Static Path Segment]/[Dynamic Segment]/[More Static or Dynamic Segments]

Example URL: https://github.com/:user_id/repos

1. Static Path Segment: 'repos'

   • A fixed part of the URL path that doesn't change.

2. Dynamic Segment: :user_id

   • A variable part of the URL. The user_id can be any value, representing a specific user.

Challenge: Enhance the TrieRouter Class to Support Dynamic Routing

In this challenge, we will modify the existing TrieRouter class to support dynamic routing. Dynamic routes are identified by segments of the URL that begin with a colon (:), allowing for variable parameters in the route paths. This enhancement will enable the router to extract these dynamic parameters and make them accessible to the corresponding route handler.

Requirements

1. Dynamic Route Identification: Modify the #addRoute method to recognize dynamic route segments (e.g., /users/:userId) and store them appropriately within the RouteNode.

2. Parameter Extraction: Update the findRoute method to extract dynamic parameters from the URL path and return them alongside the route handler.

3. Data Structure Update: Enhance the RouteNode class to include a property for storing dynamic parameter names.

4. Error Handling: Ensure that the router continues to validate paths and handlers, throwing appropriate errors for malformed paths or invalid HTTP methods.

More Details

1. Dynamic Parameter Storage: In the RouteNode class, add a params property to store the names of dynamic parameters for each route.

2. Route Addition Logic: In the #addRoute method, check if a segment starts with a colon (:). If it does, treat it as a dynamic parameter and store its name in the params array of the current node.

3. Route Finding Logic: In the findRoute method, when a dynamic segment is encountered, extract the corresponding value from the URL and store it somewhere for later use.

4. Example:

   • Input: "/users/:userId"
   • Output: When the path "/users/123" is requested, the router should return { params: { userId: '123' }, handler: <handler_function> }.

Solution

Here’s the updated implementation of the TrieRouter class with dynamic routing capabilities:

const HTTP_METHODS = {
  GET: "GET",
  POST: "POST",
  PUT: "PUT",
  DELETE: "DELETE",
  PATCH: "PATCH",
  HEAD: "HEAD",
  OPTIONS: "OPTIONS",
  CONNECT: "CONNECT",
  TRACE: "TRACE",
};

class RouteNode {
  constructor() {
    this.children = new Map();
    this.handler = new Map();
    this.params = [];
  }
}

class TrieRouter {
  constructor() {
    this.root = new RouteNode();
  }

  #verifyParams(path, method, handler) {
    if (typeof path !== "string" || path[0] !== "/") throw new Error("Malformed path provided.");
    if (typeof handler !== "function") throw new Error("Handler should be a function");
    if (!HTTP_METHODS[method]) throw new Error("Invalid HTTP Method");
  }

  #addRoute(path, method, handler) {
    this.#verifyParams(path, method, handler);

    let currentNode = this.root;
    let routeParts = path.split("/").filter(Boolean);
    let dynamicParams = [];

    for (const segment of routeParts) {
      if (segment.includes(" ")) throw new Error("Malformed `path` parameter");

      const isDynamic = segment[0] === ":";
      const key = isDynamic ? ":" : segment.toLowerCase();

      if (isDynamic) {
        dynamicParams.push(segment.substring(1));
      }

      if (!currentNode.children.has(key)) {
        currentNode.children.set(key, new RouteNode());
      }

      currentNode = currentNode.children.get(key);
    }

    currentNode.handler.set(method, handler);
    currentNode.params = dynamicParams;
  }

  findRoute(path, method) {
    let segments = path.split("/").filter(Boolean);
    let currentNode = this.root;
    let extractedParams = [];

    for (let idx = 0; idx < segments.length; idx++) {
      const segment = segments[idx];

      let childNode = currentNode.children.get(segment.toLowerCase());
      if (childNode) {
        currentNode = childNode;
      } else if ((childNode = currentNode.children.get(":"))) {
        extractedParams.push(segment);
        currentNode = childNode;
      } else {
        return null;
      }
    }

    let params = Object.create(null);

    for (let idx = 0; idx < extractedParams.length; idx++) {
      let key = currentNode.params[idx];
      let value = extractedParams[idx];

      params[key] = value;
    }

    return {
      params,
      handler: currentNode.handler.get(method),
    };
  }

  get(path, handler) {
    this.#addRoute(path, HTTP_METHODS.GET, handler);
  }

  post(path, handler) {
    this.#addRoute(path, HTTP_METHODS.POST, handler);
  }

  put(path, handler) {
    this.#addRoute(path, HTTP_METHODS.PUT, handler);
  }

  delete(path, handler) {
    this.#addRoute(path, HTTP_METHODS.DELETE, handler);
  }

  patch(path, handler) {
    this.#addRoute(path, HTTP_METHODS.PATCH, handler);
  }

  head(path, handler) {
    this.#addRoute(path, HTTP_METHODS.HEAD, handler);
  }

  options(path, handler) {
    this.#addRoute(path, HTTP_METHODS.OPTIONS, handler);
  }

  connect(path, handler) {
    this.#addRoute(path, HTTP_METHODS.CONNECT, handler);
  }

  trace(path, handler) {
    this.#addRoute(path, HTTP_METHODS.TRACE, handler);
  }

  printTree(node = this.root, indentation = 0) {
    const indent = "-".repeat(indentation);

    node.children.forEach((childNode, segment) => {
      console.log(`${indent}(${segment}) Dynamic: ${childNode.params}`);
      this.printTree(childNode, indentation + 1);
    });
  }
}

Let's go through the updated code and understand the changes made to support dynamic routing in the TrieRouter.

Explanation

class RouteNode {
  constructor() {
    this.children = new Map();
    this.handler = new Map();

    // Initialize an array to store dynamic parameter names
    this.params = [];
  }
}

In the RouteNode class, we added a params array to store the names of dynamic parameters. This allows us to keep track of which segments of the route are dynamic (e.g., :userId) and helps in extracting their values when a matching route is found.

class TrieRouter {
  constructor() {
    // Create a root node upon TrieRouter instantiation
    this.root = new RouteNode();
  }
}

The TrieRouter constructor remains unchanged, still initializing a root node that serves as the entry point for route management.

##verifyParams(path, method, handler) {
  if (typeof path !== "string" || path[0] !== "/") throw new Error("Malformed path provided.");
  if (typeof handler !== "function") throw new Error("Handler should be a function");
  if (!HTTP_METHODS[method]) throw new Error("Invalid HTTP Method");
}

We introduced a new private method #verifyParams to validate the parameters passed to the addRoute method. This method checks that the path is a valid string starting with a slash, that the handler is a function, and that the method is a valid HTTP method. This way we separate the validation logic from the main route handling logic.

##addRoute(path, method, handler) {
  this.#verifyParams(path, method, handler);

  let currentNode = this.root;
  let routeParts = path.split("/").filter(Boolean);
  let dynamicParams = [];
}

In the #addRoute method, we call #verifyParams to validate the inputs. We also initialize an array dynamicParams to keep track of any dynamic segments in the route.

for (const segment of routeParts) {
  if (segment.includes(" ")) throw new Error("Malformed `path` parameter");

  const isDynamic = segment[0] === ":";
  const key = isDynamic ? ":" : segment.toLowerCase();

  if (isDynamic) {
    dynamicParams.push(segment.substring(1));
  }

As we iterate through each segment of the route, we check if it is dynamic by looking for a leading colon (:). If it is dynamic, we store the parameter name (without the colon) in the dynamicParams array. We also determine the key to use in the children Map: if it's dynamic, we use ":" as the key; otherwise, we convert the segment to lowercase.

if (!currentNode.children.has(key)) {
  currentNode.children.set(key, new RouteNode());
}

If a child node for the current segment does not exist, we create a new RouteNode and add it to the children Map of the current node.

currentNode.handler.set(method, handler);
currentNode.params = dynamicParams;

After processing all segments, we set the handler for the route in the handler Map and store the dynamic parameters in the params array of the current node.

findRoute(path, method) {
  let segments = path.split("/").filter(Boolean);
  let currentNode = this.root;
  let extractedParams = [];

  ...
}

In the findRoute method, we initialize an array extractedParams to store values for any dynamic parameters. Note that we store the "keys" of the dynamic parameter in the addRoute method and the "values" in the findRoute method.

for (let idx = 0; idx < segments.length; idx++) {
  const segment = segments[idx];

  let childNode = currentNode.children.get(segment.toLowerCase());
  if (childNode) {
    currentNode = childNode;
  } else if ((childNode = currentNode.children.get(":"))) {
    extractedParams.push(segment);
    currentNode = childNode;
  } else {
    return null;
  }
}

As we iterate through the segments, we first check for a direct match in the children Map. If no match is found, we check for a dynamic route (using the ":" key). If we find a dynamic route, we push the current segment's value into extractedParams.

Note the syntax (childNode = currentNode.children.get(":")). This is a common pattern in JavaScript to both check if a value is truthy and assign it to a variable in a single line. So,

let x = obj.get("key");
if (x) {
  // do something with x
}

can be written as

if ((x = obj.get("key"))) {
  // do something with x
}

Now, moving on to extracting the dynamic parameters:

let params = Object.create(null);

for (let idx = 0; idx < extractedParams.length; idx++) {
  let key = currentNode.params[idx];
  let value = extractedParams[idx];

  params[key] = value;
}

After traversing the route, we create an object params to store the extracted dynamic parameters. We loop through extractedParams and map each value to its corresponding key from currentNode.params.

return {
  params,
  handler: currentNode.handler.get(method),
};

Finally, we return an object containing the extracted parameters and the corresponding handler for the route.

Testing the implementation

I've also updated the printTree method to include dynamic parameters in the output. You can use this method to visualize the trie structure and verify that dynamic routes are correctly stored.

const trieRouter = new TrieRouter();
trieRouter.get("/users/:id/hello/there/:some/:hello", function get1() {});
trieRouter.post("/users/:some/hello/there/:id/none", function post1() {});

console.log("Printing Tree:");
trieRouter.printTree();

console.log("Finding Handlers:");

console.log(trieRouter.findRoute("/users/e/hello/there/2/3", HTTP_METHODS.GET));
console.log(trieRouter.findRoute("/users/1/hello/there/2/none", HTTP_METHODS.GET));
console.log(trieRouter.findRoute("/users", HTTP_METHODS.PUT));
console.log(trieRouter.findRoute("/users", HTTP_METHODS.TRACE));

This outputs:

Printing Tree:
(users) Dynamic:
-(:) Dynamic:
--(hello) Dynamic:
---(there) Dynamic:
----(:) Dynamic:
-----(:) Dynamic: id,some,hello
-----(none) Dynamic: some,id

Finding Handlers:
{
  params: [Object: null prototype] { id: 'e', some: '2', hello: '3' },
  handler: [Function: get1]
}
{
  params: [Object: null prototype] { some: '1', id: '2' },
  handler: undefined
}
{ params: [Object: null prototype] {}, handler: undefined }
{ params: [Object: null prototype] {}, handler: undefined }

That's it! We now have a TrieRouter that supports dynamic routing, allowing us to define routes with variable segments and extract their values when a route is matched.

Visualisation of our TrieRouter structure

Suppose we have the following routes:

trieRouter.get("/users/:id", function get1() {});
trieRouter.get("/users/:id/ban", function get1() {});
trieRouter.get("/:some/hello", function post2() {});
trieRouter.get("/:name/student", function get3() {});

The trie structure would look like this:

Summary

In this challenge, we successfully enhanced the TrieRouter class to support dynamic routing. The router can now handle routes with dynamic parameters, extract their values from the URL, and provide them to the corresponding route handler. This functionality is essential for building flexible and scalable web applications.