find-my-way - npm Package Compare versions

		'use strict'

		const assert = require('assert')
		const deepEqual = require('fast-deep-equal')
		const HandlerStorage = require('./handler_storage')

		const types = {
		const NODE_TYPES = {
		STATIC: 0,
		PARAM: 1,
		MATCH_ALL: 2,
		REGEX: 3
		PARAMETRIC: 1,
		WILDCARD: 2
		}

		function Node (options) {
		options = options \|\| {}
		this.prefix = options.prefix \|\| '/'
		this.label = this.prefix[0]
		this.method = options.method // not used for logic, just for debugging and pretty printing
		this.handlers = options.handlers \|\| [] // unoptimized list of handler objects for which the fast matcher function will be compiled
		this.unconstrainedHandler = options.unconstrainedHandler \|\| null // optimized reference to the handler that will match most of the time
		this.staticChildren = options.staticChildren \|\| {}
		this.numberOfChildren = Object.keys(this.staticChildren).length
		this.kind = options.kind \|\| this.types.STATIC
		this.regex = options.regex \|\| null
		this.wildcardChild = null
		this.parametricChild = null
		this.wildcardBrother = null
		this.parametricBrother = null
		this.constrainer = options.constrainer
		this.hasConstraints = options.hasConstraints \|\| false
		this.constrainedHandlerStores = null
		}

		Object.defineProperty(Node.prototype, 'types', {
		value: types
		})

		Node.prototype.addChild = function (node) {
		const label = node.prefix[0]
		switch (node.kind) {
		case this.types.STATIC:
		assert(
		this.staticChildren[label] === undefined,
		`There is already a child with label '${label}'`
		)
		this.staticChildren[label] = node
		break
		case this.types.PARAM:
		case this.types.REGEX:
		assert(this.parametricChild === null, 'There is already a parametric child')
		this.parametricChild = node
		break
		case this.types.MATCH_ALL:
		assert(this.wildcardChild === null, 'There is already a wildcard child')
		this.wildcardChild = node
		break
		default:
		throw new Error(`Unknown node kind: ${node.kind}`)
		class Node {
		constructor () {
		this.handlerStorage = new HandlerStorage()
		}

		this.numberOfChildren++

		this._saveParametricBrother()
		this._saveWildcardBrother()

		return this
		}

		Node.prototype._saveParametricBrother = function () {
		let parametricBrother = this.parametricBrother
		if (this.parametricChild !== null) {
		this.parametricChild.parametricBrother = parametricBrother
		parametricBrother = this.parametricChild
		class ParentNode extends Node {
		constructor () {
		super()
		this.staticChildren = {}
		}

		// Save the parametric brother inside static children
		if (parametricBrother) {
		for (const child of Object.values(this.staticChildren)) {
		child.parametricBrother = parametricBrother
		child._saveParametricBrother(parametricBrother)
		findStaticMatchingChild (path, pathIndex) {
		const staticChild = this.staticChildren[path.charAt(pathIndex)]
		if (staticChild === undefined) {
		return null
		}
		}
		}

		Node.prototype._saveWildcardBrother = function () {
		let wildcardBrother = this.wildcardBrother
		if (this.wildcardChild !== null) {
		this.wildcardChild.wildcardBrother = wildcardBrother
		wildcardBrother = this.wildcardChild
		for (let i = 0; i < staticChild.prefix.length; i++) {
		if (path.charCodeAt(pathIndex + i) !== staticChild.prefix.charCodeAt(i)) {
		return null
		}
		}
		return staticChild
		}

		// Save the wildcard brother inside static children
		if (wildcardBrother) {
		for (const child of Object.values(this.staticChildren)) {
		child.wildcardBrother = wildcardBrother
		child._saveWildcardBrother(wildcardBrother)
		createStaticChild (path) {
		if (path.length === 0) {
		return this
		}
		if (this.parametricChild !== null) {
		this.parametricChild.wildcardBrother = wildcardBrother
		}
		}
		}

		Node.prototype.reset = function (prefix) {
		this.prefix = prefix
		this.staticChildren = {}
		this.handlers = []
		this.unconstrainedHandler = null
		this.kind = this.types.STATIC
		this.numberOfChildren = 0
		this.regex = null
		this.wildcardChild = null
		this.parametricChild = null
		this.hasConstraints = false
		this._decompileGetHandlerMatchingConstraints()
		return this
		}

		Node.prototype.split = function (length) {
		const newChild = new Node(
		{
		prefix: this.prefix.slice(length),
		staticChildren: this.staticChildren,
		kind: this.kind,
		method: this.method,
		handlers: this.handlers.slice(0),
		regex: this.regex,
		constrainer: this.constrainer,
		hasConstraints: this.hasConstraints,
		unconstrainedHandler: this.unconstrainedHandler
		let staticChild = this.staticChildren[path.charAt(0)]
		if (staticChild) {
		let i = 0
		for (; i < staticChild.prefix.length; i++) {
		if (path.charCodeAt(i) !== staticChild.prefix.charCodeAt(i)) {
		staticChild = staticChild.split(this, i)
		break
		}
		}
		return staticChild.createStaticChild(path.slice(i))
		}
		)

		if (this.wildcardChild !== null) {
		newChild.wildcardChild = this.wildcardChild
		const label = path.charAt(0)
		this.staticChildren[label] = new StaticNode(path)
		return this.staticChildren[label]
		}

		if (this.parametricChild !== null) {
		newChild.parametricChild = this.parametricChild
		}

		this.reset(this.prefix.slice(0, length))
		this.addChild(newChild)
		return newChild
		}

		Node.prototype.getChildByLabel = function (label, kind) {
		if (label.length === 0) {
		return null
		class StaticNode extends ParentNode {
		constructor (prefix) {
		super()
		this.prefix = prefix
		this.wildcardChild = null
		this.parametricChild = null
		this.kind = NODE_TYPES.STATIC
		}

		switch (kind) {
		case this.types.STATIC:
		return this.staticChildren[label]
		case this.types.MATCH_ALL:
		return this.wildcardChild
		case this.types.PARAM:
		case this.types.REGEX:
		createParametricChild (regex) {
		if (this.parametricChild) {
		return this.parametricChild
		}
		}

		Node.prototype.findStaticMatchingChild = function (path, pathIndex) {
		const child = this.staticChildren[path[pathIndex]]
		if (child !== undefined) {
		for (let i = 0; i < child.prefix.length; i++) {
		if (path.charCodeAt(pathIndex + i) !== child.prefix.charCodeAt(i)) {
		return null
		}
		}
		return child
		}
		return null
		}

		Node.prototype.addHandler = function (handler, params, store, constraints) {
		if (!handler) return
		assert(!this.getHandler(constraints), `There is already a handler with constraints '${JSON.stringify(constraints)}' and method '${this.method}'`)

		const handlerObject = {
		handler: handler,
		params: params,
		constraints: constraints,
		store: store \|\| null,
		paramsLength: params.length
		this.parametricChild = new ParametricNode(regex)
		return this.parametricChild
		}

		this.handlers.push(handlerObject)
		// Sort the most constrained handlers to the front of the list of handlers so they are tested first.
		this.handlers.sort((a, b) => Object.keys(a.constraints).length - Object.keys(b.constraints).length)
		createWildcardChild () {
		if (this.wildcardChild) {
		return this.wildcardChild
		}

		if (Object.keys(constraints).length > 0) {
		this.hasConstraints = true
		} else {
		this.unconstrainedHandler = handlerObject
		this.wildcardChild = new WildcardNode()
		return this.wildcardChild
		}

		if (this.hasConstraints && this.handlers.length > 32) {
		throw new Error('find-my-way supports a maximum of 32 route handlers per node when there are constraints, limit reached')
		}
		split (parentNode, length) {
		const parentPrefix = this.prefix.slice(0, length)
		const childPrefix = this.prefix.slice(length)

		// Note that the fancy constraint handler matcher needs to be recompiled now that the list of handlers has changed
		// This lazy compilation means we don't do the compile until the first time the route match is tried, which doesn't waste time re-compiling every time a new handler is added
		this._decompileGetHandlerMatchingConstraints()
		}
		this.prefix = childPrefix

		Node.prototype.getHandler = function (constraints) {
		return this.handlers.filter(handler => deepEqual(constraints, handler.constraints))[0]
		}
		const staticNode = new StaticNode(parentPrefix)
		staticNode.staticChildren[childPrefix.charAt(0)] = this
		parentNode.staticChildren[parentPrefix.charAt(0)] = staticNode

		// We compile the handler matcher the first time this node is matched. We need to recompile it if new handlers are added, so when a new handler is added, we reset the handler matching function to this base one that will recompile it.
		function compileThenGetHandlerMatchingConstraints (derivedConstraints) {
		this._compileGetHandlerMatchingConstraints()
		return this._getHandlerMatchingConstraints(derivedConstraints)
		}

		// This is the hot path for node handler finding -- change with care!
		Node.prototype.getMatchingHandler = function (derivedConstraints) {
		if (derivedConstraints === undefined) {
		return this.unconstrainedHandler
		return staticNode
		}

		if (this.hasConstraints) {
		// This node is constrained, use the performant precompiled constraint matcher
		return this._getHandlerMatchingConstraints(derivedConstraints)
		}

		// This node doesn't have any handlers that are constrained, so it's handlers probably match. Some requests have constraint values that must match however, like version, so check for those before returning it.
		if (!derivedConstraints.__hasMustMatchValues) {
		return this.unconstrainedHandler
		}

		return null
		}

		// Slot for the compiled constraint matching function
		Node.prototype._getHandlerMatchingConstraints = compileThenGetHandlerMatchingConstraints

		Node.prototype._decompileGetHandlerMatchingConstraints = function () {
		this._getHandlerMatchingConstraints = compileThenGetHandlerMatchingConstraints
		return null
		}

		// Builds a store object that maps from constraint values to a bitmap of handler indexes which pass the constraint for a value
		// So for a host constraint, this might look like { "fastify.io": 0b0010, "google.ca": 0b0101 }, meaning the 3rd handler is constrainted to fastify.io, and the 2nd and 4th handlers are constrained to google.ca.
		// The store's implementation comes from the strategies provided to the Router.
		Node.prototype._buildConstraintStore = function (constraint) {
		const store = this.constrainer.newStoreForConstraint(constraint)

		for (let i = 0; i < this.handlers.length; i++) {
		const handler = this.handlers[i]
		const mustMatchValue = handler.constraints[constraint]
		if (typeof mustMatchValue !== 'undefined') {
		let indexes = store.get(mustMatchValue)
		if (!indexes) {
		indexes = 0
		}
		indexes \|= 1 << i // set the i-th bit for the mask because this handler is constrained by this value https://stackoverflow.com/questions/1436438/how-do-you-set-clear-and-toggle-a-single-bit-in-javascrip
		store.set(mustMatchValue, indexes)
		}
		class ParametricNode extends ParentNode {
		constructor (regex) {
		super()
		this.regex = regex \|\| null
		this.isRegex = !!regex
		this.kind = NODE_TYPES.PARAMETRIC
		}

		return store
		}

		// Builds a bitmask for a given constraint that has a bit for each handler index that is 0 when that handler is constrained and 1 when the handler isnt constrainted. This is opposite to what might be obvious, but is just for convienience when doing the bitwise operations.
		Node.prototype._constrainedIndexBitmask = function (constraint) {
		let mask = 0b0
		for (let i = 0; i < this.handlers.length; i++) {
		const handler = this.handlers[i]
		if (handler.constraints && constraint in handler.constraints) {
		mask \|= 1 << i
		}
		class WildcardNode extends Node {
		constructor () {
		super()
		this.kind = NODE_TYPES.WILDCARD
		}
		return ~mask
		}

		// Compile a fast function to match the handlers for this node
		// The function implements a general case multi-constraint matching algorithm.
		// The general idea is this: we have a bunch of handlers, each with a potentially different set of constraints, and sometimes none at all. We're given a list of constraint values and we have to use the constraint-value-comparison strategies to see which handlers match the constraint values passed in.
		// We do this by asking each constraint store which handler indexes match the given constraint value for each store. Trickily, the handlers that a store says match are the handlers constrained by that store, but handlers that aren't constrained at all by that store could still match just fine. So, each constraint store can only describe matches for it, and it won't have any bearing on the handlers it doesn't care about. For this reason, we have to ask each stores which handlers match and track which have been matched (or not cared about) by all of them.
		// We use bitmaps to represent these lists of matches so we can use bitwise operations to implement this efficiently. Bitmaps are cheap to allocate, let us implement this masking behaviour in one CPU instruction, and are quite compact in memory. We start with a bitmap set to all 1s representing every handler that is a match candidate, and then for each constraint, see which handlers match using the store, and then mask the result by the mask of handlers that that store applies to, and bitwise AND with the candidate list. Phew.
		// We consider all this compiling function complexity to be worth it, because the naive implementation that just loops over the handlers asking which stores match is quite a bit slower.
		Node.prototype._compileGetHandlerMatchingConstraints = function () {
		this.constrainedHandlerStores = {}
		let constraints = new Set()
		for (const handler of this.handlers) {
		for (const key of Object.keys(handler.constraints)) {
		constraints.add(key)
		}
		}
		constraints = Array.from(constraints)
		const lines = []

		// always check the version constraint first as it is the most selective
		constraints.sort((a, b) => a === 'version' ? 1 : 0)

		for (const constraint of constraints) {
		this.constrainedHandlerStores[constraint] = this._buildConstraintStore(constraint)
		}

		lines.push(`
		let candidates = 0b${'1'.repeat(this.handlers.length)}
		let mask, matches
		`)
		for (const constraint of constraints) {
		// Setup the mask for indexes this constraint applies to. The mask bits are set to 1 for each position if the constraint applies.
		lines.push(`
		mask = ${this._constrainedIndexBitmask(constraint)}
		value = derivedConstraints.${constraint}
		`)

		// If there's no constraint value, none of the handlers constrained by this constraint can match. Remove them from the candidates.
		// If there is a constraint value, get the matching indexes bitmap from the store, and mask it down to only the indexes this constraint applies to, and then bitwise and with the candidates list to leave only matching candidates left.
		lines.push(`
		if (typeof value === "undefined") {
		candidates &= mask
		} else {
		matches = this.constrainedHandlerStores.${constraint}.get(value) \|\| 0
		candidates &= (matches \| mask)
		}
		if (candidates === 0) return null;
		`)
		}
		// Return the first handler who's bit is set in the candidates https://stackoverflow.com/questions/18134985/how-to-find-index-of-first-set-bit
		lines.push(`
		const handler = this.handlers[Math.floor(Math.log2(candidates))]
		if (handler && derivedConstraints.__hasMustMatchValues && handler === this.unconstrainedHandler) {
		return null;
		}
		return handler;
		`)

		this._getHandlerMatchingConstraints = new Function('derivedConstraints', lines.join('\n')) // eslint-disable-line
		}

		module.exports = Node
		module.exports = { StaticNode, ParametricNode, WildcardNode, NODE_TYPES }

328

index.js

		@@ -32,7 +32,7 @@ 'use strict'
		const { flattenNode, compressFlattenedNode, prettyPrintFlattenedNode, prettyPrintRoutesArray } = require('./lib/pretty-print')
		const Node = require('./custom_node')
		const { StaticNode, NODE_TYPES } = require('./custom_node')
		const Constrainer = require('./lib/constrainer')
		const sanitizeUrl = require('./lib/url-sanitizer')
		const HandlerStorage = require('./handler_storage')

		const NODE_TYPES = Node.prototype.types
		const httpMethods = http.METHODS
		@@ -86,5 +86,7 @@ const FULL_PATH_REGEXP = /^https?:\/\/.*?\//
		this.allowUnsafeRegex = opts.allowUnsafeRegex \|\| false
		this.routes = []
		this.trees = {}

		this.constrainer = new Constrainer(opts.constraints)
		this.trees = {}
		this.routes = []
		HandlerStorage.prototype.constrainer = this.constrainer
		}
		@@ -120,17 +122,12 @@

		const methods = Array.isArray(method) ? method : [method]
		const paths = [path]
		const route = path

		if (this.ignoreTrailingSlash && path !== '/' && !path.endsWith('*')) {
		if (path.endsWith('/')) {
		paths.push(path.slice(0, -1))
		} else {
		paths.push(path + '/')
		}
		if (this.ignoreTrailingSlash) {
		path = trimLastSlash(path)
		}

		for (const path of paths) {
		for (const method of methods) {
		this._on(method, path, opts, handler, store)
		}
		const methods = Array.isArray(method) ? method : [method]
		for (const method of methods) {
		this._on(method, path, opts, handler, store, route)
		this.routes.push({ method, path, opts, handler, store })
		}
		@@ -155,42 +152,46 @@ }

		this.routes.push({ method, path, opts, handler, store })

		// Boot the tree for this method if it doesn't exist yet
		let currentNode = this.trees[method]
		if (typeof currentNode === 'undefined') {
		currentNode = new Node({ method: method, constrainer: this.constrainer })
		this.trees[method] = currentNode
		if (this.trees[method] === undefined) {
		this.trees[method] = new StaticNode('/')
		}

		if (!path.startsWith('/') && currentNode.prefix !== '') {
		currentNode.split(0)
		if (path === '*' && this.trees[method].prefix.length !== 0) {
		const currentRoot = this.trees[method]
		this.trees[method] = new StaticNode('')
		this.trees[method].staticChildren['/'] = currentRoot
		}

		let parentNodePathIndex = this.trees[method].prefix.length
		let currentNode = this.trees[method]
		let parentNodePathIndex = currentNode.prefix.length

		const params = []
		for (let i = 0; i <= path.length; i++) {
		// search for parametric or wildcard routes
		// parametric route
		if (path.charCodeAt(i) === 58) {
		if (path.charCodeAt(i + 1) === 58) {
		// It's a double colon. Let's just replace it with a single colon and go ahead
		path = path.slice(0, i) + path.slice(i + 1)
		continue
		if (path.charCodeAt(i) === 58 && path.charCodeAt(i + 1) === 58) {
		// It's a double colon. Let's just replace it with a single colon and go ahead
		path = path.slice(0, i) + path.slice(i + 1)
		continue
		}

		const isParametricNode = path.charCodeAt(i) === 58
		const isWildcardNode = path.charCodeAt(i) === 42

		if (isParametricNode \|\| isWildcardNode \|\| (i === path.length && i !== parentNodePathIndex)) {
		let staticNodePath = path.slice(parentNodePathIndex, i)
		if (!this.caseSensitive) {
		staticNodePath = staticNodePath.toLowerCase()
		}

		// add the static part of the route to the tree
		currentNode = this._insert(currentNode, method, path.slice(parentNodePathIndex, i), NODE_TYPES.STATIC, null)
		currentNode = currentNode.createStaticChild(staticNodePath)
		}

		const paramStartIndex = i + 1

		if (isParametricNode) {
		let isRegexNode = false
		const regexps = []
		let nodeType = NODE_TYPES.PARAM
		let lastParamStartIndex = paramStartIndex

		for (let j = paramStartIndex; ; j++) {
		let lastParamStartIndex = i + 1
		for (let j = lastParamStartIndex; ; j++) {
		const charCode = path.charCodeAt(j)

		if (charCode === 40 \|\| charCode === 45 \|\| charCode === 46) {
		nodeType = NODE_TYPES.REGEX
		isRegexNode = true

		@@ -240,3 +241,3 @@ const paramName = path.slice(lastParamStartIndex, j)
		if (path.charCodeAt(j) === 47 \|\| j === path.length) {
		path = path.slice(0, paramStartIndex) + path.slice(j)
		path = path.slice(0, i + 1) + path.slice(j)
		break
		@@ -247,53 +248,20 @@ }
		let regex = null
		if (nodeType === NODE_TYPES.REGEX) {
		if (isRegexNode) {
		regex = new RegExp('^' + regexps.join('') + '$')
		}

		currentNode = this._insert(currentNode, method, ':', nodeType, regex)
		currentNode = currentNode.createParametricChild(regex)
		parentNodePathIndex = i + 1
		// wildcard route
		} else if (path.charCodeAt(i) === 42) {
		currentNode = this._insert(currentNode, method, path.slice(parentNodePathIndex, i), NODE_TYPES.STATIC, null)
		} else if (isWildcardNode) {
		// add the wildcard parameter
		params.push('*')
		currentNode = this._insert(currentNode, method, path.slice(i), NODE_TYPES.MATCH_ALL, null)
		break
		} else if (i === path.length && i !== parentNodePathIndex) {
		currentNode = this._insert(currentNode, method, path.slice(parentNodePathIndex), NODE_TYPES.STATIC, null)
		currentNode = currentNode.createWildcardChild()
		parentNodePathIndex = i + 1
		}
		}

		assert(!currentNode.getHandler(constraints), `Method '${method}' already declared for route '${path}' with constraints '${JSON.stringify(constraints)}'`)
		currentNode.addHandler(handler, params, store, constraints)
		assert(!currentNode.handlerStorage.getHandler(constraints), `Method '${method}' already declared for route '${path}' with constraints '${JSON.stringify(constraints)}'`)
		currentNode.handlerStorage.addHandler(handler, params, store, constraints)
		}

		Router.prototype._insert = function _insert (currentNode, method, path, kind, regex) {
		if (!this.caseSensitive) {
		path = path.toLowerCase()
		}

		let childNode = currentNode.getChildByLabel(path.charAt(0), kind)
		while (childNode) {
		currentNode = childNode

		let i = 0
		for (; i < currentNode.prefix.length; i++) {
		if (path.charCodeAt(i) !== currentNode.prefix.charCodeAt(i)) {
		currentNode.split(i)
		break
		}
		}
		path = path.slice(i)
		childNode = currentNode.getChildByLabel(path.charAt(0), kind)
		}

		if (path.length > 0) {
		const node = new Node({ method, prefix: path, kind, handlers: null, regex, constrainer: this.constrainer })
		currentNode.addChild(node)
		currentNode = node
		}

		return currentNode
		}

		Router.prototype.reset = function reset () {
		@@ -305,13 +273,2 @@ this.trees = {}
		Router.prototype.off = function off (method, path) {
		var self = this

		if (Array.isArray(method)) {
		return method.map(function (method) {
		return self.off(method, path)
		})
		}

		// method validation
		assert(typeof method === 'string', 'Method should be a string')
		assert(httpMethods.indexOf(method) !== -1, `Method '${method}' is not an http method.`)
		// path validation
		@@ -335,29 +292,26 @@ assert(typeof path === 'string', 'Path should be a string')

		if (this.ignoreTrailingSlash) {
		path = trimLastSlash(path)
		}

		const methods = Array.isArray(method) ? method : [method]
		for (const method of methods) {
		this._off(method, path)
		}
		}

		Router.prototype._off = function _off (method, path) {
		// method validation
		assert(typeof method === 'string', 'Method should be a string')
		assert(httpMethods.includes(method), `Method '${method}' is not an http method.`)

		// Rebuild tree without the specific route
		const ignoreTrailingSlash = this.ignoreTrailingSlash
		var newRoutes = self.routes.filter(function (route) {
		if (!ignoreTrailingSlash) {
		return !(method === route.method && path === route.path)
		}
		if (path.endsWith('/')) {
		const routeMatches = path === route.path \|\| path.slice(0, -1) === route.path
		return !(method === route.method && routeMatches)
		}
		const routeMatches = path === route.path \|\| (path + '/') === route.path
		return !(method === route.method && routeMatches)
		})
		if (ignoreTrailingSlash) {
		newRoutes = newRoutes.filter(function (route, i, ar) {
		if (route.path.endsWith('/') && i < ar.length - 1) {
		return route.path.slice(0, -1) !== ar[i + 1].path
		} else if (route.path.endsWith('/') === false && i < ar.length - 1) {
		return (route.path + '/') !== ar[i + 1].path
		}
		return true
		})
		const newRoutes = this.routes.filter((route) => method !== route.method \|\| path !== route.path)
		this.reset()

		for (const route of newRoutes) {
		const { method, path, opts, handler, store } = route
		this._on(method, path, opts, handler, store)
		this.routes.push({ method, path, opts, handler, store })
		}
		self.reset()
		newRoutes.forEach(function (route) {
		self.on(route.method, route.path, route.opts, route.handler, route.store)
		})
		}
		@@ -389,2 +343,6 @@

		if (this.ignoreTrailingSlash) {
		path = trimLastSlash(path)
		}

		if (this.caseSensitive === false) {
		@@ -406,3 +364,3 @@ path = path.toLowerCase()
		if (pathIndex === pathLen) {
		const handle = currentNode.getMatchingHandler(derivedConstraints)
		const handle = currentNode.handlerStorage.getMatchingHandler(derivedConstraints)

		@@ -427,23 +385,34 @@ if (handle !== null && handle !== undefined) {

		let node = currentNode.findStaticMatchingChild(path, pathIndex)
		let node = null

		if (currentNode.parametricChild !== null) {
		if (node === null) {
		node = currentNode.parametricChild
		} else {
		parametricBrothersStack.push({
		brotherPathIndex: pathIndex,
		paramsCount: params.length
		})
		}
		}
		if (
		currentNode.kind === NODE_TYPES.STATIC \|\|
		currentNode.kind === NODE_TYPES.PARAMETRIC
		) {
		node = currentNode.findStaticMatchingChild(path, pathIndex)

		if (currentNode.wildcardChild !== null) {
		if (node === null) {
		node = currentNode.wildcardChild
		} else {
		wildcardBrothersStack.push({
		brotherPathIndex: pathIndex,
		paramsCount: params.length
		})
		if (currentNode.kind === NODE_TYPES.STATIC) {
		if (currentNode.parametricChild !== null) {
		if (node === null) {
		node = currentNode.parametricChild
		} else {
		parametricBrothersStack.push({
		brotherPathIndex: pathIndex,
		paramsCount: params.length,
		brotherNode: currentNode.parametricChild
		})
		}
		}

		if (currentNode.wildcardChild !== null) {
		if (node === null) {
		node = currentNode.wildcardChild
		} else {
		wildcardBrothersStack.push({
		brotherPathIndex: pathIndex,
		paramsCount: params.length,
		brotherNode: currentNode.wildcardChild
		})
		}
		}
		}
		@@ -454,6 +423,4 @@ }
		let brotherNodeState
		node = currentNode.parametricBrother
		if (node === null) {
		node = currentNode.wildcardBrother
		if (node === null) {
		if (parametricBrothersStack.length === 0) {
		if (wildcardBrothersStack.length === 0) {
		return null
		@@ -468,52 +435,63 @@ }
		params.splice(brotherNodeState.paramsCount)
		node = brotherNodeState.brotherNode
		}

		currentNode = node
		const kind = node.kind

		// static route
		if (kind === NODE_TYPES.STATIC) {
		pathIndex += node.prefix.length
		if (currentNode.kind === NODE_TYPES.STATIC) {
		pathIndex += currentNode.prefix.length
		continue
		}

		let paramEndIndex = kind === NODE_TYPES.MATCH_ALL ? pathLen : pathIndex

		for (; paramEndIndex < pathLen; paramEndIndex++) {
		if (path.charCodeAt(paramEndIndex) === 47) {
		break
		if (currentNode.kind === NODE_TYPES.WILDCARD) {
		const decoded = sanitizedUrl.sliceParameter(pathIndex)
		if (decoded === null) {
		return this._onBadUrl(path.slice(pathIndex))
		}
		}

		const decoded = sanitizedUrl.sliceParameter(pathIndex, paramEndIndex)
		if (decoded === null) {
		return this._onBadUrl(path.slice(pathIndex, paramEndIndex))
		}

		if (
		kind === NODE_TYPES.PARAM \|\|
		kind === NODE_TYPES.MATCH_ALL
		) {
		if (decoded.length > maxParamLength) {
		return null
		}

		params.push(decoded)
		pathIndex = pathLen
		continue
		}

		if (kind === NODE_TYPES.REGEX) {
		const matchedParameters = node.regex.exec(decoded)
		if (matchedParameters === null) {
		return null
		if (currentNode.kind === NODE_TYPES.PARAMETRIC) {
		let paramEndIndex = pathIndex
		for (; paramEndIndex < pathLen; paramEndIndex++) {
		if (path.charCodeAt(paramEndIndex) === 47) {
		break
		}
		}

		for (let i = 1; i < matchedParameters.length; i++) {
		const param = matchedParameters[i]
		if (param.length > maxParamLength) {
		const decoded = sanitizedUrl.sliceParameter(pathIndex, paramEndIndex)
		if (decoded === null) {
		return this._onBadUrl(path.slice(pathIndex, paramEndIndex))
		}

		if (currentNode.isRegex) {
		const matchedParameters = currentNode.regex.exec(decoded)
		if (matchedParameters === null) {
		return null
		}
		params.push(param)

		for (let i = 1; i < matchedParameters.length; i++) {
		const param = matchedParameters[i]
		if (param.length > maxParamLength) {
		return null
		}
		params.push(param)
		}
		} else {
		if (decoded.length > maxParamLength) {
		return null
		}
		params.push(decoded)
		}

		pathIndex = paramEndIndex
		}

		pathIndex = paramEndIndex
		}
		@@ -554,5 +532,6 @@ }

		for (const node of Object.values(this.trees)) {
		for (const method in this.trees) {
		const node = this.trees[method]
		if (node) {
		flattenNode(root, node)
		flattenNode(root, node, method)
		}
		@@ -589,2 +568,9 @@ }

		function trimLastSlash (path) {
		if (path.length > 1 && path.charCodeAt(path.length - 1) === 47) {
		return path.slice(0, -1)
		}
		return path
		}

		function trimRegExpStartAndEnd (regexString) {
		@@ -591,0 +577,0 @@ // removes chars that marks start "^" and end "$" of regexp

lib/pretty-print.js

		@@ -192,5 +192,5 @@ 'use strict'

		for (const node of flattenedNode.nodes) {
		for (const handler of node.handlers) {
		printHandlers.push({ method: node.method, ...handler })
		for (const { node, method } of flattenedNode.nodes) {
		for (const handler of node.handlerStorage.handlers) {
		printHandlers.push({ method, ...handler })
		}
		@@ -252,35 +252,49 @@ }

		function flattenNode (flattened, node) {
		if (node.handlers.length > 0) {
		flattened.nodes.push(node)
		function flattenNode (flattened, node, method) {
		if (node.handlerStorage.handlers.length > 0) {
		flattened.nodes.push({ method, node })
		}

		const nodeChildren = Object.values(node.staticChildren)

		if (node.parametricChild) {
		nodeChildren.unshift(node.parametricChild)
		if (!flattened.children[':']) {
		flattened.children[':'] = {
		prefix: ':',
		nodes: [],
		children: {}
		}
		}
		flattenNode(flattened.children[':'], node.parametricChild, method)
		}

		if (node.wildcardChild) {
		nodeChildren.unshift(node.wildcardChild)
		if (!flattened.children['*']) {
		flattened.children['*'] = {
		prefix: '*',
		nodes: [],
		children: {}
		}
		}
		flattenNode(flattened.children['*'], node.wildcardChild, method)
		}

		for (const child of nodeChildren) {
		// split on the slash separator but use a regex to lookahead and not actually match it, preserving it in the returned string segments
		const childPrefixSegments = child.prefix.split(pathRegExp)
		let cursor = flattened
		let parent
		for (const segment of childPrefixSegments) {
		parent = cursor
		cursor = cursor.children[segment]
		if (!cursor) {
		cursor = {
		prefix: segment,
		nodes: [],
		children: {}
		if (node.staticChildren) {
		for (const child of Object.values(node.staticChildren)) {
		// split on the slash separator but use a regex to lookahead and not actually match it, preserving it in the returned string segments
		const childPrefixSegments = child.prefix.split(pathRegExp)
		let cursor = flattened
		let parent
		for (const segment of childPrefixSegments) {
		parent = cursor
		cursor = cursor.children[segment]
		if (!cursor) {
		cursor = {
		prefix: segment,
		nodes: [],
		children: {}
		}
		parent.children[segment] = cursor
		}
		parent.children[segment] = cursor
		}
		flattenNode(cursor, child, method)
		}
		flattenNode(cursor, child)
		}
		@@ -287,0 +301,0 @@ }

package.json

		{
		"name": "find-my-way",
		"version": "5.4.1",
		"version": "5.5.0",
		"description": "Crazy fast http radix based router",
		@@ -5,0 +5,0 @@ "main": "index.js",

test/errors.test.js

		@@ -208,3 +208,3 @@ 'use strict'
		} catch (e) {
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test/\' with constraints \'{}\'')
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test\' with constraints \'{}\'')
		}
		@@ -230,3 +230,3 @@ })
		} catch (e) {
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test/\' with constraints \'{}\'')
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test\' with constraints \'{}\'')
		}
		@@ -274,3 +274,3 @@ })
		} catch (e) {
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test/hello/\' with constraints \'{}\'')
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test/hello\' with constraints \'{}\'')
		}
		@@ -311,5 +311,5 @@ })
		} catch (e) {
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test/hello/\' with constraints \'{}\'')
		t.equal(e.message, 'Method \'GET\' already declared for route \'/test/hello\' with constraints \'{}\'')
		}
		})
		})

test/issue-104.test.js

		@@ -6,3 +6,2 @@ 'use strict'
		const FindMyWay = require('../')
		const Node = require('../custom_node')

		@@ -210,19 +209,1 @@ test('Nested static parametric route, url with parameter common prefix > 1', t => {
		})

		test('parametricBrother of Parent Node, with a parametric child', t => {
		t.plan(1)
		const parent = new Node({ prefix: '/a' })
		const parametricChild = new Node({ prefix: ':id', kind: parent.types.PARAM })
		parent.addChild(parametricChild)
		t.equal(parent.parametricBrother, null)
		})

		test('parametricBrother of Parent Node, with a parametric child and a static child', t => {
		t.plan(1)
		const parent = new Node({ prefix: '/a' })
		const parametricChild = new Node({ prefix: ':id', kind: parent.types.PARAM })
		const staticChild = new Node({ prefix: '/b', kind: parent.types.STATIC })
		parent.addChild(parametricChild)
		parent.addChild(staticChild)
		t.equal(parent.parametricBrother, null)
		})

test/methods.test.js

		@@ -151,9 +151,9 @@ 'use strict'
		findMyWay.on('GET', '/test1/', () => {})
		t.equal(findMyWay.routes.length, 2)
		t.equal(findMyWay.routes.length, 1)

		findMyWay.on('GET', '/test2', () => {})
		t.equal(findMyWay.routes.length, 4)
		t.equal(findMyWay.routes.length, 2)

		findMyWay.off('GET', '/test1')
		t.equal(findMyWay.routes.length, 2)
		t.equal(findMyWay.routes.length, 1)
		t.equal(
		@@ -165,3 +165,3 @@ findMyWay.routes.filter((r) => r.path === '/test2').length,
		findMyWay.routes.filter((r) => r.path === '/test2/').length,
		1
		0
		)
		@@ -168,0 +168,0 @@

Improved metrics

Worsened metrics