Trie and Smart Routers

Copyexport class TrieRouter<T> implements Router<T> {
  name: string = 'TrieRouter'
  #node: Node<T>
 
  constructor() {
    this.#node = new Node()
  }
...

Copy  add(method: string, path: string, handler: T) {
    const results = checkOptionalParameter(path)
    if (results) {
      for (let i = 0, len = results.length; i < len; i++) {
        this.#node.insert(method, results[i], handler)
      }
      return
    }
 
    this.#node.insert(method, path, handler)
  }

Copy  match(method: string, path: string): Result<T> {
    return this.#node.search(method, path)
  }

Copyexport class Node<T> {
  #methods: Record<string, HandlerSet<T>>[]
 
  #children: Record<string, Node<T>>
  #patterns: Pattern[]
  #order: number = 0
  #params: Record<string, string> = emptyParams
 
  constructor(method?: string, handler?: T, children?: Record<string, Node<T>>) {
    this.#children = children || Object.create(null)
    this.#methods = []
    if (method && handler) {
      const m: Record<string, HandlerSet<T>> = Object.create(null)
      m[method] = { handler, possibleKeys: [], score: 0 }
      this.#methods = [m]
    }
    this.#patterns = []
  }

Copyinsert(method: string, path: string, handler: T): Node<T> {
  this.#order = ++this.#order
 
  // eslint-disable-next-line @typescript-eslint/no-this-alias
  let curNode: Node<T> = this
  const parts = splitRoutingPath(path)
 
  const possibleKeys: string[] = []
 
  for (let i = 0, len = parts.length; i < len; i++) {
    const p: string = parts[i]
    const nextP = parts[i + 1]
    const pattern = getPattern(p, nextP)
    const key = Array.isArray(pattern) ? pattern[0] : p
 
    if (key in curNode.#children) {
      curNode = curNode.#children[key]
      if (pattern) {
        possibleKeys.push(pattern[1])
      }
      continue
    }

Copy 
    curNode.#children[key] = new Node()
 
    if (pattern) {
      curNode.#patterns.push(pattern)
      possibleKeys.push(pattern[1])
    }
    curNode = curNode.#children[key]
  }
 
  curNode.#methods.push({
    [method]: {
      handler,
      possibleKeys: possibleKeys.filter((v, i, a) => a.indexOf(v) === i),
      score: this.#order,
    },
  })
 
  return curNode
}

Copysearch(method: string, path: string): [[T, Params][]] {
  const handlerSets: HandlerParamsSet<T>[] = []
  this.#params = emptyParams
 
  // eslint-disable-next-line @typescript-eslint/no-this-alias
  const curNode: Node<T> = this
  let curNodes = [curNode]
  const parts = splitPath(path)
  const curNodesQueue: Node<T>[][] = []
 
  const len = parts.length
  let partOffsets: number[] | null = null
 

Copyfor (let i = 0; i < len; i++) {
  const part: string = parts[i]
  const isLast = i === len - 1
  const tempNodes: Node<T>[] = []
 
  for (let j = 0, len2 = curNodes.length; j < len2; j++) {
    const node = curNodes[j]
    const nextNode = node.#children[part]
 
    if (nextNode) {
      nextNode.#params = node.#params
      if (isLast) {
        // '/hello/*' => match '/hello'
        if (nextNode.#children['*']) {
          this.#pushHandlerSets(handlerSets, nextNode.#children['*'], method, node.#params)
        }
        this.#pushHandlerSets(handlerSets, nextNode, method, node.#params)
      } else {
        tempNodes.push(nextNode)
      }
    }
 

Copyconst [key, name, matcher] = pattern
 
if (!part && !(matcher instanceof RegExp)) {
  continue
}
 
const child = node.#children[key]
 
// `/js/:filename{[a-z]+.js}` => match /js/chunk/123.js
if (matcher instanceof RegExp) {
  if (partOffsets === null) {
    partOffsets = new Array(len)
    let offset = path[0] === '/' ? 1 : 0
    for (let p = 0; p < len; p++) {
      partOffsets[p] = offset
      offset += parts[p].length + 1
    }
  }
  const restPathString = path.substring(partOffsets[i])
 
  const m = matcher.exec(restPathString)
  if (m) {
    params[name] = m[0]
    this.#pushHandlerSets(handlerSets, child, method, node.#params, params)
 
    if (hasChildren(child.#children)) {
      child.#params = params
      const componentCount = m[0].match(/\//)?.length ?? 0
      const targetCurNodes = (curNodesQueue[componentCount] ||= [])
      targetCurNodes.push(child)
    }
 
    continue
  }
}
 
if (matcher === true || matcher.test(part)) {
  params[name] = part
  if (isLast) {

Copy#pushHandlerSets(
  handlerSets: HandlerParamsSet<T>[],
  node: Node<T>,
  method: string,
  nodeParams: Record<string, string>,
  params?: Record<string, string>
): void {
  for (let i = 0, len = node.#methods.length; i < len; i++) {
    const m = node.#methods[i]
    const handlerSet = (m[method] || m[METHOD_NAME_ALL]) as HandlerParamsSet<T>
    const processedSet: Record<number, boolean> = {}
    if (handlerSet !== undefined) {
      handlerSet.params = Object.create(null)
      handlerSets.push(handlerSet)
      if (nodeParams !== emptyParams || (params && params !== emptyParams)) {
        for (let i = 0, len = handlerSet.possibleKeys.length; i < len; i++) {
          const key = handlerSet.possibleKeys[i]
          const processed = processedSet[handlerSet.score]
          handlerSet.params[key] =
            params?.[key] && !processed ? params[key] : (nodeParams[key] ?? params?.[key])
          processedSet[handlerSet.score] = true
        }
      }
    }
  }
}

Copyexport class SmartRouter<T> implements Router<T> {
  name: string = 'SmartRouter'
  #routers: Router<T>[] = []
  #routes?: [string, string, T][] = []
 
  constructor(init: { routers: Router<T>[] }) {
    this.#routers = init.routers
  }
 
  add(method: string, path: string, handler: T) {
    if (!this.#routes) {
      throw new Error(MESSAGE_MATCHER_IS_ALREADY_BUILT)
    }
 
    this.#routes.push([method, path, handler])
  }
 

Copymatch(method: string, path: string): Result<T> {
  if (!this.#routes) {
    throw new Error('Fatal error')
  }
 
  const routers = this.#routers
  const routes = this.#routes
 
  const len = routers.length
  let i = 0
  let res
  for (; i < len; i++) {
    const router = routers[i]
    try {
      for (let i = 0, len = routes.length; i < len; i++) {
        router.add(...routes[i])
      }
      res = router.match(method, path)
    } catch (e) {
      if (e instanceof UnsupportedPathError) {
        continue
      }
      throw e
    }
 
    this.match = router.match.bind(router)
    this.#routers = [router]
    this.#routes = undefined
    break
  }
 

Copyexport class SmartRouter<T> implements Router<T> {
  name: string = 'SmartRouter'
  #routers: Router<T>[] = []
  #routes?: [string, string, T][] = []
 
  constructor(init: { routers: Router<T>[] }) {
    this.#routers = init.routers
  }

Copyconst routers = this.#routers
const routes = this.#routes
 
const len = routers.length
let i = 0
let res
for (; i < len; i++) {
  const router = routers[i]
  try {
    for (let i = 0, len = routes.length; i < len; i++) {
      router.add(...routes[i])
    }
    res = router.match(method, path)
  } catch (e) {
    if (e instanceof UnsupportedPathError) {
      continue
    }
    throw e
  }
 
  this.match = router.match.bind(router)
  this.#routers = [router]
  this.#routes = undefined
  break
}

Copytry {
  for (let i = 0, len = routes.length; i < len; i++) {
    router.add(...routes[i])
  }
  res = router.match(method, path)
} catch (e) {
  if (e instanceof UnsupportedPathError) {
    continue
  }
  throw e
}