experimental-router.js

/*
  how dynamic paths work

  while this design sounds good, may wish to consider allowing something like
    {param|/regex/}
  would require the existance of "DynNode" to store the regex validator
  but also, the parent Node would need to store an array of DynNodes
  don't need to store the param names though, since it can be stored in the dynnodes themselves
  when adding, must verify the names match up

  how to detect something like

  /{this}/{that}
  conflicts with
  /{something}/{else}?
  the original method of storing param names in the leaves "solves" this since the router would notice
    a handler already exists for the /{}/{} node, no matter the params

  still could use an array for the DynNodes, but the *only* deciding factor will be the regex
  these could simply be stored in the order they arrive.
  I suppose potentially more ideally, the regex's could be sorted by most specific to least.
  without true regex analysis, this is difficult. a toString().length could be the best thing for now

  supporting something like
    routes:
      /aboutus
      /{page}/hello
      /{function}/{action}

    looks like
      /
        children: [aboutus: {handler: fn}]
        dyn: [
          {
            regex: null
            children: [hello:{params: ['page'], handler: fn}]
            dyn: empty
          },
          {
            regex: null
            children: empty
            dyn: [
              {
                regex: null
                children: empty
                dyn: empty
                params: ['function', 'action']
                handler: fn
              }
            ]
          },
        ]


    /aboutus should go to: /aboutus
    /aboutus/hello should go /{page}/hello
    /aboutus/idfgs should go /{function}/{action}

    / would know it has a dynamic path. to avoid loops, could keep the param names at the leaves

    when adding, do not resolve dynamic parts. just verify the regex and paths match or new node
    maybe different searches after all for add and match is necessary since they vary

    when adding a route:
      immediately look for a '{', verify it follows '/', verify there is a '}' and either empty or '/'
        remember where the ending is
      resolve the left portion (non-dynamic parts) [recursive? maybe just a function called before node search]
      if the last node does not have a dynNode, make one. else continue from the dynNode
      if the } is at the end, then set the handler and params for dynNode
      if the } is not at the end, then continue processing after the end

    when matching a route:
      go as normal as far as possible. when encountering nodes with a dynNode, push them to a stack
      if we did not resolve the route && the dynstack is not empty, pop and continue with the dynNode

    a DynNode is never assumed to end in a slash
    there should be a node with the / on it

*/

(function(root, factory) {
  if (typeof define === "function" && define.amd) {
    define([], factory);
  } else if (typeof exports === "object") {
    module.exports = factory();
  } else {
    root.TrieRouter = factory();
  }
}(this, function() {
  'use strict'

  // Class node
  //  + chCode: integer (not set for dynamic nodes)
  //  + str: string (the path part. for dynamic nodes, this is null)
  //  + regex: regex (only set for dynamic nodes and may still be null)
  //  + children: [Node] (must be sorted for binary search)
  //  + dynamicNodes: [Node] (must be sorted where this.regex.toString().length is DESC; order of complexity)
  //  + handlers: {method: [fn(req, res, next?)]}
  function Node(str, regex) {
    this.str = str;
    this.regex = regex;
    this.chCode = str ? str.charCodeAt(0) : -1;
    this.children = [];
    this.dynamicPath = [];
    this.params = null;
    this.handlers = {};
  }

  Node.prototype.addHandler = function(methods, handler) {
    for (var i = methods.length; i--;) {
      var method = methods[i].toLowerCase();
      if (this.handlers[method]) {
        // TODO: they already have one! they may have done one something wrong
        console.log('already have one?');
        return;
      }

      this.handlers[method] = handler;
    }
  };

  Node.prototype.insertChild = function(node) {
    var i = this.children.length;
    for (;i--;) {
      if (this.children[i].chCode < node.chCode) { break; }
    }
    this.children.splice(i+1, 0, node);
  };

  Node.prototype.insertDynamicNode = function(node) {
    this.dynamicPath.push(node);
  };

  // must create the initial root node. does help when '/' isn't the first declared route
  var rootNode = new Node('/');

  // chCode must also be obtained through chatCodeAt to be an int
  function binarySearch(children, chCode) {
    var lb = 0;
    var ub = children.length - 1;
    var mid = 0;
    var node = null;
    var d = 0;
    var diff = 0;

    while (true) {
      d = ub - lb;
      if (d < 0) {
        break;
      }
      mid = (d >> 1) + lb;
      node = children[mid];
      diff = node.chCode - chCode;

      if (diff === 0) {
        return node;
      } else if (diff < 0) {
        lb = mid + 1;
      } else {
        ub = mid - 1;
      }
    }

    return null;
  }

  // never pass a dynamic part to this. only static parts
  function findNodeForAdd(startNode, path) {
    var result = {
      node: null,
      lastIndex: -1,
      isPartialMatch: false
    };

    var strLength = path.length;
    var rootLength = startNode.str ? startNode.str.length : 0;

    if (strLength === rootLength && path === startNode.str) {
      result.node = startNode;
      return result;
    }

    var i = rootLength;
    var nexti = 0;

    var curNode = startNode;
    var lastNode = null;
    var curChildren = curNode.children;
    var matchStr = null;

    while (curNode && i < strLength) {
      lastNode = curNode;
      curNode = binarySearch(curChildren, path.charCodeAt(i));

      if (!curNode) {
        result.node = lastNode;
        result.lastIndex = i;
        break;
      }

      matchStr = curNode.str;
      nexti = i + matchStr.length;

      // make sure the remaining path is long enough to match, then verify the match
      if (nexti > strLength || matchStr !== path.substring(i, nexti)) {
        result.node = curNode;
        result.lastIndex = i;
        result.isPartialMatch = true;
        break;
      }

      i = nexti;

      if (i < strLength) {
        curChildren = curNode.children;

        if (!curChildren.length) {
          result.node = curNode;
          result.lastIndex = i;
          break;
        }
      } else {
        result.node = curNode;
        break;
      }
    }

    return result;
  }

  function addNodes(startNode, path, options) {
    if (!startNode && !rootNode) {
      var newNode = new Node(path, false);
      rootNode = newNode;

      return rootNode;
    }

    // get the parent node (or a node to split)
    var result = findNodeForAdd(startNode, path);
    var newNode = null;

    if (!result.node) {
      // theoretically, this isn't possible if canBePartial is 1. we will at least get the root
      // don't really want a panic though
      // TODO: throw me
      return null;
    }

    if (result.lastIndex !== -1 && result.lastIndex < path.length) {
      // there be splittin that needs to happen
      if (result.isPartialMatch) {
        // has remaining and partial means either node.str is longer OR two strings start with some base string

        var i1, i2;
        for (i1 = result.lastIndex, i2 = 0; path[i1] === result.node.str[i2] && i1 < path.length; i1++, i2++) {}

        // it's possible i1 could be at the end of path
        // i2 cannot be at the end of result.node.str
        // or i1 and i2 could just be in the middle of both strings

        /*
          we start by creating a new node to hold the remainder of result.node.str
          move the children array, handlers, etc over.

          modify the original node to contain only the shared, base string,
          start with fresh children array, no handlers, etc.
          add the new node as the first child.

          finally, if there's any i1 remaining, create a new node for it.
          else, just add the handler to the now-modified "original" node.
        */

        var i2Node = new Node(result.node.str.slice(i2), false);
        i2Node.children = result.node.children;
        i2Node.handlers = result.node.handlers;

        result.node.str = result.node.str.slice(0, i2);
        result.node.chCode = result.node.str.charCodeAt(0);
        result.node.children = [i2Node];
        result.node.handlers = {};

        if (i1 === path.length) {
          newNode = result.node;
        } else {
          newNode = new Node(path.slice(i1), false);
          result.node.insertChild(newNode);
        }
      } else {
        newNode = new Node(path.slice(result.lastIndex), false);
        result.node.insertChild(newNode);
      }
    } else {
      return result.node;
    }

    return newNode;
  }

  function addPath(methods, path, handler, options) {
    var lastIndex = 0;
    var dynIndex = 0;
    var endDynIndex = 0;
    var params = [];
    var node = rootNode;

    while ((lastIndex = endDynIndex) < path.length && (dynIndex = path.indexOf('{', lastIndex)) !== -1) {
      if (path[dynIndex-1] !== '/') {
        // TODO: error
        return false;
      }

      // TODO: improve finding the end of the regex. maybe need a regex to properly handle ((())) moments
      // need to check for regex and where it ends to properly know the end brace in case the regex uses braces
      var regexSepIndex = path.indexOf('(', dynIndex + 1);
      var regexEndIndex = regexSepIndex === -1 ? -1 : path.indexOf(')', regexSepIndex);
      if (regexSepIndex !== -1 && regexEndIndex === -1) {
        // TODO: error
        return false;
      }

      endDynIndex = path.indexOf('}', regexEndIndex === -1 ? dynIndex : regexEndIndex) + 1;
      if (endDynIndex === 0 || !(endDynIndex === path.length || path[endDynIndex] === '/')) {
        // TODO: error
        return false;
      }

      // process the nodes leading to the DynNode
      node = addNodes(node, path.slice(lastIndex, dynIndex), options);
      if (!node) {
        // TODO: error
        return false;
      }

      // push the param name to an array
      var paramName = null;
      var regex = null;

      if (regexSepIndex !== -1 && regexEndIndex !== -1) {
        paramName = path.slice(dynIndex + 1, regexSepIndex);
        regex = new RegExp(path.slice(regexSepIndex + 1, regexEndIndex));
      } else {
        paramName = path.slice(dynIndex + 1, endDynIndex - 1);
      }
      // TODO: validate paramname is legit
      params.push(paramName);

      // check if a dyn already exists and also figure out the insert location
      var i = 0;
      for (; i < node.dynamicPath.length; i++) {
        var dyn = node.dynamicPath[i];

        if ((dyn.regex === null && regex === null) || (dyn.regex !== null && regex !== null && dyn.regex.toString() === regex.toString())) {
          node = dyn;
          i = -1;
          break;
        }

        if (dyn.regex === null && regex !== null) {
          break;
        }

        if (dyn.regex !== null && regex !== null && dyn.regex.toString().length < regex.toString().length) {
          break;
        }
      }

      // add a new one if there's no match
      if (i !== -1) {
        var newNode = new Node(null, regex);
        node.dynamicPath.splice(i, 0, newNode);
        node = newNode;
      }
    }

    // if there's remaining (also if there was no dyn at all), process the rest
    if (lastIndex < path.length) {
      node = addNodes(rootNode, path.slice(lastIndex), options);
    }

    if (!node) {
      // TODO: error
      return false;
    }

    // add handler to very last node and set params if they exists
    node.params = params;
    node.addHandler(methods, handler);

    return true;
  }

  function matchPathToNode(path, method) {
    var strLength = path.length;
    var rootLength = rootNode.str.length;

    if (strLength === rootLength && path === rootNode.str) {
      return {node: rootNode, vars: []};
    }

    var i = rootLength;
    var nexti = 0;

    var curNode = rootNode;
    var lastNode = null;
    var curChildren = curNode.children;
    var matchStr = null;
    var dynStack = [];
    var dynStackLength;
    // dynVars: {i: int, data: string}
    var dynVars = [];

    while (curNode && i < strLength) {
      /*
        if curNode has dyn, push to dynStack
        do a children count check.
        if no children, do a dyn-attempt
        if has children, do search on children
        if no match, do dyn-attempt
      */
      dynStackLength = dynStack.length;
      if (curNode.dynamicPath.length && (dynStackLength === 0 || dynStack[dynStackLength-1].node !== curNode)) {
        dynStack.push({i: i, node: curNode, j: 0});
        dynStackLength++;
      }

      curChildren = curNode.children;
      var needDynCheck = false;
      if (!curChildren.length) {
        needDynCheck = true;
      } else {
        curNode = binarySearch(curChildren, path.charCodeAt(i));

        if (!curNode) {
          needDynCheck = true;
        } else {
          matchStr = curNode.str;
          nexti = i + matchStr.length;

          // make sure the remaining path is long enough to match, then verify the match
          if (nexti > strLength || matchStr !== path.substring(i, nexti)) {
            needDynCheck = true;
          } else {
            // always possible we reached a valid node, yet it has no handler for the method
            if (nexti === strLength && !curNode.handlers[method]) {
              needDynCheck = true;
            } else {
              i = nexti;
            }
          }
        }
      }

      if (needDynCheck) {
        // prevents a potential infinite loop
        curNode = null;
        while (dynStackLength) {
          var dyninfo = dynStack.pop();

          var dynnode = dyninfo.node;
          var slashPathIndex = path.indexOf('/', dyninfo.i);
          var nextPathPart = slashPathIndex === -1 ? path.slice(dyninfo.i) : path.slice(dyninfo.i, slashPathIndex);

          // check if a dyn matches
          for (var j = dyninfo.j, dyncount = dynnode.dynamicPath.length; j < dyncount; j++) {
            var dyn = dynnode.dynamicPath[j];

            if (!dyn.regex || dyn.regex.test(nextPathPart)) {
              nexti = dyninfo.i + nextPathPart.length;
              if (nexti === strLength && !dyn.handlers[method]) {
                // skip it, shouldn't try to end on one without a handler if at all possible
                continue;
              }

              dynVars.push({i: i, data: nextPathPart});
              curNode = dyn;
              i = nexti;

              // might need to process the other dynnodes
              if (++j < dyncount) {
                dyninfo.j = j;
                dynStack.push(dyninfo);
              }

              break;
            }
          }
          if (curNode) {
            break;
          }
          for (var dynvarLength = dynVars.length; dynvarLength--;) {
            if (i < dynVars[i].i) {
              dynVars.pop();
            }
          }
          // may have to loop and try other dyn nodes
        }

        if (curNode) {
          continue;
        } else {
          return null;
        }
      }
    }

    var reqparams = {};
    if (dynVars.length && dynVars.length === curNode.params.length) {
      for (var dv = 0; dv < dynVars.length; dv++) {
        reqparams[curNode.params[dv]] = dynVars[dv].data;
      }
    }

    return i === strLength ? {node: curNode, vars: reqparams} : null;
  }


  // only used for debuging help
  function printNode(node) {
    console.log(JSON.stringify(node, null, 2));
  }

  // public interface
  var TrieRouter = {
    // config now similar to Hapi
    add: function(config) {
      if (!config.methods) {
        // TODO: error
        console.log('methods does not exist');
        return false;
      }
      if (!config.path || !(typeof(config.path) === 'string')) {
        // TODO: error
        console.log('path does not exist or is not a string', config.path);
        return false;
      }
      if (!config.handler || !(config.handler instanceof Function)) {
        // TODO: error
        console.log('handler does not exist or is not a function');
        return false;
      }

      var methods = config.methods;
      if (!(methods instanceof Array)) {
        if (typeof(config.path) === 'string') {
          methods = [methods];
        } else {
          // TODO: error
          console.log('methods must be either an array or a string');
          return false;
        }
      }

      // TODO: figure out the pre/post and generate a single fn to send
      addPath(methods, config.path, config.handler, config.options);
    },

    handle: function(request, result) {
      var method = request.method.toLowerCase();
      var path = request.url;

      var matchInfo = matchPathToNode(path, method);

      if (!matchInfo || !matchInfo.node) {
        // TODO: 404
        console.log('nothing found, 404');
        return;
      }
      var node = matchInfo.node;

      if (!Object.keys(node.handlers).length) {
        // TODO: 404
        console.log('path has no handlers, 404');
        return;
      }

      var handler = node.handlers[method];

      if (!handler) {
        printNode(node);
        // TODO: check sec rules to see if we return 405 or 404/403
        console.log('405 method not allowed');
        return;
      }

      // TODO: check sec rules to make sure this is ok
      request.params = matchInfo.vars;
      handler(request, result);
    },

    print: function() {
      printNode(rootNode);
    }
  };

  return TrieRouter;
}));