1/*
2 * MIT License
3 *
4 * Copyright (c) 2017-2019 Tomas Della Vedova
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24
25import type * as Router from "../../FindMyWay.ts"
26import * as QS from "./queryString.ts"
27
28const FULL_PATH_REGEXP = /^https?:\/\/.*?\//
29const OPTIONAL_PARAM_REGEXP = /(\/:[^/()]*?)\?(\/?)/
30
31const emptyParamsArray: ReadonlyArray<string> = []
32
33// Matches one terminal parameter without wildcard, regex, or static suffix syntax.
34const CLEAN_SINGLE_PARAM_REGEXP = /^[^:*(]*\/:[^/:*(.-]+$/
35const isCleanSingleTrailingParam = (path: string): boolean => CLEAN_SINGLE_PARAM_REGEXP.test(path)
36
37interface Route<A = unknown> {
38 readonly method: string
39 readonly path: Router.PathInput
40 readonly pattern: string
41 readonly handler: A
42 readonly params: ReadonlyArray<string>
43}
44
45/**
46 * @internal
47 */
48export const make = <A>(
49 options: Partial<Router.RouterConfig> = {}
50): Router.Router<A> => new RouterImpl(options)
51
52class RouterImpl<A> implements Router.Router<A> {
53 constructor(options: Partial<Router.RouterConfig> = {}) {
54 this.options = {
55 ignoreTrailingSlash: true,
56 ignoreDuplicateSlashes: true,
57 caseSensitive: false,
58 maxParamLength: 100,
59 ...options
60 }
61 }
62
63 readonly options: Router.RouterConfig
64 routes: Array<Route> = []
65 trees: Record<string, StaticNode> = Object.create(null)
66 staticRoutes: Record<string, Map<string, Handler>> = Object.create(null)
67 singleParamRoutes: Record<string, Map<string, Handler>> = Object.create(null)
68 singleParamDisabled: Record<string, boolean> = Object.create(null)
69 readonly brothersNodesStack: Array<BrotherNode> = []
70 readonly singleParamArray: Array<string> = [""]
71
72 on(
73 method: string | Iterable<string>,
74 path: Router.PathInput,
75 handler: A
76 ): void {
77 const optionalParamMatch = path.match(OPTIONAL_PARAM_REGEXP)
78 if (optionalParamMatch && optionalParamMatch.index !== undefined) {
79 assert(
80 path.length === optionalParamMatch.index + optionalParamMatch[0].length,
81 "Optional Parameter needs to be the last parameter of the path"
82 )
83
84 const pathFull = path.replace(
85 OPTIONAL_PARAM_REGEXP,
86 "$1$2"
87 ) as Router.PathInput
88 const pathOptional = (path.replace(
89 OPTIONAL_PARAM_REGEXP,
90 "$2"
91 ) || "/") as Router.PathInput
92
93 this.on(method, pathFull, handler)
94 this.on(method, pathOptional, handler)
95 return
96 }
97
98 if (this.options.ignoreDuplicateSlashes) {
99 path = removeDuplicateSlashes(path)
100 }
101
102 if (this.options.ignoreTrailingSlash) {
103 path = trimLastSlash(path)
104 }
105
106 const methods = typeof method === "string" ? [method] : method
107 for (const method of methods) {
108 this._on(method, path, handler)
109 }
110 }
111
112 all(path: Router.PathInput, handler: A) {
113 this.on(httpMethods, path, handler)
114 }
115
116 private _on(method: string, path: Router.PathInput, handler: A): void {
117 if (this.trees[method] === undefined) {
118 this.trees[method] = new StaticNode("/")
119 }
120
121 let pattern = path
122 if (pattern === "*" && this.trees[method].prefix.length !== 0) {
123 const currentRoot = this.trees[method]
124 this.trees[method] = new StaticNode("")
125 this.trees[method].staticChildren["/"] = currentRoot
126 }
127
128 let parentNodePathIndex = this.trees[method].prefix.length
129 let currentNode: Node = this.trees[method]
130
131 const params = []
132 for (let i = 0; i <= pattern.length; i++) {
133 if (pattern.charCodeAt(i) === 58 && pattern.charCodeAt(i + 1) === 58) {
134 // It's a double colon
135 i++
136 continue
137 }
138
139 const isParametricNode = pattern.charCodeAt(i) === 58 && pattern.charCodeAt(i + 1) !== 58
140 const isWildcardNode = pattern.charCodeAt(i) === 42
141
142 if (
143 isParametricNode ||
144 isWildcardNode ||
145 (i === pattern.length && i !== parentNodePathIndex)
146 ) {
147 let staticNodePath = pattern.slice(parentNodePathIndex, i)
148 if (!this.options.caseSensitive) {
149 staticNodePath = staticNodePath.toLowerCase()
150 }
151 staticNodePath = staticNodePath.split("::").join(":")
152 staticNodePath = staticNodePath.split("%").join("%25")
153 // add the static part of the route to the tree
154 currentNode = (currentNode as StaticNode).createStaticChild(
155 staticNodePath
156 )
157 }
158
159 if (isParametricNode) {
160 let isRegexNode = false
161 let isParamSafe = true
162 let backtrack = ""
163 const regexps = []
164 let nodePatternParts = ""
165
166 let lastParamStartIndex = i + 1
167 for (let j = lastParamStartIndex;; j++) {
168 const charCode = pattern.charCodeAt(j)
169
170 const isRegexParam = charCode === 40
171 const isStaticPart = charCode === 45 || charCode === 46
172 const isEndOfNode = charCode === 47 || j === pattern.length
173
174 if (isRegexParam || isStaticPart || isEndOfNode) {
175 const paramName = pattern.slice(lastParamStartIndex, j)
176 params.push(paramName)
177
178 isRegexNode = isRegexNode || isRegexParam || isStaticPart
179
180 if (isRegexParam) {
181 const endOfRegexIndex = getClosingParenthensePosition(pattern, j)
182 const regexString = pattern.slice(j, endOfRegexIndex + 1)
183
184 regexps.push(trimRegExpStartAndEnd(regexString))
185
186 j = endOfRegexIndex + 1
187 isParamSafe = true
188 } else {
189 regexps.push(isParamSafe ? "(.*?)" : `(${backtrack}|(?:(?!${backtrack}).)*)`)
190 isParamSafe = false
191 }
192
193 const staticPartStartIndex = j
194 for (; j < pattern.length; j++) {
195 const charCode = pattern.charCodeAt(j)
196 if (charCode === 47) break
197 if (charCode === 58) {
198 const nextCharCode = pattern.charCodeAt(j + 1)
199 if (nextCharCode === 58) j++
200 else break
201 }
202 }
203
204 let staticPart = pattern.slice(staticPartStartIndex, j)
205 if (staticPart) {
206 staticPart = staticPart.split("::").join(":")
207 staticPart = staticPart.split("%").join("%25")
208 regexps.push(backtrack = escapeRegExp(staticPart))
209 }
210
211 lastParamStartIndex = j + 1
212 nodePatternParts += "()" + staticPart
213
214 if (
215 isEndOfNode ||
216 pattern.charCodeAt(j) === 47 ||
217 j === pattern.length
218 ) {
219 const nodePattern = isRegexNode ? nodePatternParts : staticPart
220 const nodePath = pattern.slice(i, j)
221
222 pattern = pattern.slice(0, i + 1) + nodePattern + pattern.slice(j)
223 i += nodePattern.length
224
225 const regex = isRegexNode
226 ? new RegExp("^" + regexps.join("") + "$")
227 : undefined
228 currentNode = (currentNode as StaticNode).createParametricChild(
229 regex,
230 staticPart,
231 nodePath
232 )
233 parentNodePathIndex = i + 1
234 break
235 }
236 }
237 }
238 } else if (isWildcardNode) {
239 // add the wildcard parameter
240 params.push("*")
241 currentNode = (currentNode as StaticNode).createWildcardChild()
242 parentNodePathIndex = i + 1
243
244 if (i !== pattern.length - 1) {
245 throw new Error("Wildcard must be the last character in the route")
246 }
247 }
248 }
249
250 if (!this.options.caseSensitive) {
251 pattern = pattern.toLowerCase() as Router.PathInput
252 }
253
254 if (pattern === "*") {
255 pattern = "/*"
256 }
257
258 for (const existRoute of this.routes) {
259 if (existRoute.method === method && existRoute.pattern === pattern) {
260 throw new Error(
261 `Method '${method}' already declared for route '${pattern}'`
262 )
263 }
264 }
265
266 const route = { method, path, pattern, params, handler }
267 this.routes.push(route)
268 currentNode.addRoute(route)
269
270 // Cache static routes by normalized path for direct lookup.
271 if (params.length === 0) {
272 const staticKey = pattern.split("::").join(":").split("%").join("%25")
273 const store = this.staticRoutes[method] ??= new Map()
274 if (!store.has(staticKey)) {
275 store.set(staticKey, currentNode.handlerStorage!.unconstrainedHandler!)
276 }
277 } else if (isCleanSingleTrailingParam(path)) {
278 // Cache "/prefix/:param" routes for direct prefix matching.
279 if (this.singleParamDisabled[method] !== true) {
280 let prefix = path.slice(0, path.indexOf(":"))
281 if (!this.options.caseSensitive) {
282 prefix = prefix.toLowerCase()
283 }
284 prefix = prefix.split("%").join("%25")
285 const store = this.singleParamRoutes[method] ??= new Map()
286 if (!store.has(prefix)) {
287 store.set(prefix, currentNode.handlerStorage!.unconstrainedHandler!)
288 }
289 }
290 } else if (/[(*]|[^/]:|:[^/]*[-.]/.test(path)) {
291 // Complex parameters may shadow a cached single-parameter route.
292 this.singleParamDisabled[method] = true
293 delete this.singleParamRoutes[method]
294 }
295 }
296
297 has(method: string, path: string): boolean {
298 const node = this.trees[method]
299 if (node === undefined) {
300 return false
301 }
302
303 const staticNode = node.getStaticChild(path)
304 if (staticNode === undefined) {
305 return false
306 }
307
308 return staticNode.isLeafNode
309 }
310
311 find(method: string, path: string): Router.FindResult<A> | undefined {
312 let currentNode: Node | undefined = this.trees[method]
313 if (currentNode === undefined) return undefined
314
315 let querystring = ""
316 let shouldDecodeParam = false
317
318 // Skip normalization for canonical lowercase paths.
319 let clean = path.charCodeAt(0) === 47 &&
320 (path.length === 1 || path.charCodeAt(path.length - 1) !== 47)
321 if (clean) {
322 for (let i = 1; i < path.length; i++) {
323 const code = path.charCodeAt(i)
324 if (
325 code === 37 || code === 63 || code === 59 || code === 35 ||
326 (code >= 65 && code <= 90) ||
327 (code === 47 && path.charCodeAt(i - 1) === 47)
328 ) {
329 clean = false
330 break
331 }
332 }
333 }
334
335 if (!clean) {
336 if (path.charCodeAt(0) !== 47) {
337 // 47 is '/'
338 path = path.replace(FULL_PATH_REGEXP, "/")
339 }
340
341 // This must be run before sanitizeUrl as the resulting function
342 // .sliceParameter must be constructed with same URL string used
343 // throughout the rest of this function.
344 if (this.options.ignoreDuplicateSlashes) {
345 path = removeDuplicateSlashes(path)
346 }
347
348 let sanitizedUrl
349 try {
350 sanitizedUrl = safeDecodeURI(path)
351 path = sanitizedUrl.path
352 querystring = sanitizedUrl.querystring
353 shouldDecodeParam = sanitizedUrl.shouldDecodeParam
354 } catch (error) {
355 return undefined
356 }
357
358 if (this.options.ignoreTrailingSlash) {
359 path = trimLastSlash(path)
360 }
361 }
362
363 const originPath = path
364
365 if (!clean && this.options.caseSensitive === false) {
366 path = path.toLowerCase()
367 }
368
369 const maxParamLength = this.options.maxParamLength
370
371 const staticStore = this.staticRoutes[method]
372 if (staticStore !== undefined) {
373 const handle = staticStore.get(path)
374 if (handle !== undefined) {
375 return {
376 handler: handle.handler as A,
377 params: handle.createParams(emptyParamsArray),
378 searchParams: QS.parse(querystring)
379 } as const
380 }
381 }
382
383 const singleParamStore = this.singleParamRoutes[method]
384 if (singleParamStore !== undefined) {
385 const prefixLength = path.lastIndexOf("/") + 1
386 const handle = singleParamStore.get(path.slice(0, prefixLength))
387 if (handle !== undefined && path.length > prefixLength) {
388 let param = originPath.slice(prefixLength)
389 if (shouldDecodeParam) {
390 param = safeDecodeURIComponent(param)
391 }
392 if (param.length <= maxParamLength) {
393 this.singleParamArray[0] = param
394 return {
395 handler: handle.handler as A,
396 params: handle.createParams(this.singleParamArray),
397 searchParams: QS.parse(querystring)
398 } as const
399 }
400 }
401 }
402
403 let pathIndex = (currentNode as StaticNode).prefix.length
404 const params = []
405 const pathLen = path.length
406
407 // Reuse this router's synchronous backtracking stack.
408 const brothersNodesStack = this.brothersNodesStack
409 brothersNodesStack.length = 0
410
411 while (true) {
412 if (pathIndex === pathLen && currentNode.isLeafNode) {
413 const handle = currentNode.handlerStorage?.find()
414 if (handle !== undefined) {
415 return {
416 handler: handle.handler as A,
417 params: handle.createParams(params),
418 searchParams: QS.parse(querystring)
419 } as const
420 }
421 }
422
423 let node: Node | undefined = currentNode.getNextNode(
424 path,
425 pathIndex,
426 brothersNodesStack,
427 params.length
428 )
429
430 if (node === undefined) {
431 if (brothersNodesStack.length === 0) {
432 return undefined
433 }
434
435 const brotherNodeState = brothersNodesStack.pop()!
436 pathIndex = brotherNodeState.brotherPathIndex
437 params.splice(brotherNodeState.paramsCount)
438 node = brotherNodeState.brotherNode
439 }
440
441 currentNode = node
442
443 while (true) {
444 if (currentNode._tag === "StaticNode") {
445 pathIndex += currentNode.prefix.length
446 break
447 }
448
449 if (currentNode._tag === "WildcardNode") {
450 let param = originPath.slice(pathIndex)
451 if (shouldDecodeParam) {
452 param = safeDecodeURIComponent(param)
453 }
454
455 params.push(param)
456 pathIndex = pathLen
457 break
458 }
459
460 let paramEndIndex = originPath.indexOf("/", pathIndex)
461 if (paramEndIndex === -1) {
462 paramEndIndex = pathLen
463 }
464
465 let param = originPath.slice(pathIndex, paramEndIndex)
466 if (shouldDecodeParam) {
467 param = safeDecodeURIComponent(param)
468 }
469
470 if (currentNode.regex !== undefined) {
471 const matchedParameters: RegExpExecArray | null = currentNode.regex.exec(param)
472 if (matchedParameters === null) {
473 if (brothersNodesStack.length === 0) {
474 return undefined
475 }
476
477 const brotherNodeState = brothersNodesStack.pop()!
478 pathIndex = brotherNodeState.brotherPathIndex
479 params.splice(brotherNodeState.paramsCount)
480 currentNode = brotherNodeState.brotherNode
481 continue
482 }
483
484 let maxParamLengthExceeded = false
485 for (let i = 1; i < matchedParameters.length; i++) {
486 const matchedParam = matchedParameters[i] ?? ""
487 if (matchedParam.length > maxParamLength) {
488 maxParamLengthExceeded = true
489 break
490 }
491 }
492
493 if (maxParamLengthExceeded) {
494 if (brothersNodesStack.length === 0) {
495 return undefined
496 }
497
498 const brotherNodeState = brothersNodesStack.pop()!
499 pathIndex = brotherNodeState.brotherPathIndex
500 params.splice(brotherNodeState.paramsCount)
501 currentNode = brotherNodeState.brotherNode
502 continue
503 }
504
505 for (let i = 1; i < matchedParameters.length; i++) {
506 params.push(matchedParameters[i] ?? "")
507 }
508 } else {
509 if (param.length > maxParamLength) {
510 if (brothersNodesStack.length === 0) {
511 return undefined
512 }
513
514 const brotherNodeState = brothersNodesStack.pop()!
515 pathIndex = brotherNodeState.brotherPathIndex
516 params.splice(brotherNodeState.paramsCount)
517 currentNode = brotherNodeState.brotherNode
518 continue
519 }
520 params.push(param)
521 }
522
523 pathIndex = paramEndIndex
524 break
525 }
526 }
527 }
528}
529
530// ----------------------------------------------------------------------------
531// Handler storage
532// ----------------------------------------------------------------------------
533
534interface Handler {
535 readonly params: ReadonlyArray<string>
536 readonly handler: unknown
537 readonly createParams: (
538 paramsArray: ReadonlyArray<string>
539 ) => Record<string, string>
540}
541
542class HandlerStorage {
543 readonly handlers: Array<Handler> = []
544 unconstrainedHandler: Handler | undefined
545
546 find() {
547 return this.unconstrainedHandler
548 }
549
550 add(route: Route) {
551 const handler: Handler = {
552 params: route.params,
553 handler: route.handler,
554 createParams: makeCreateParams(route.params)
555 }
556 this.handlers.push(handler)
557 this.unconstrainedHandler = this.handlers[0]
558 }
559}
560
561// ----------------------------------------------------------------------------
562// Nodes
563// ----------------------------------------------------------------------------
564
565interface BrotherNode {
566 readonly paramsCount: number
567 readonly brotherPathIndex: number
568 readonly brotherNode: Node
569}
570
571type Node = StaticNode | ParametricNode | WildcardNode
572
573abstract class NodeBase {
574 isLeafNode = false
575 routes: Array<Route> | undefined
576 handlerStorage: HandlerStorage | undefined
577
578 addRoute(route: Route) {
579 if (this.routes === undefined) {
580 this.routes = [route]
581 } else {
582 this.routes.push(route)
583 }
584
585 if (this.handlerStorage === undefined) {
586 this.handlerStorage = new HandlerStorage()
587 }
588 this.isLeafNode = true
589 this.handlerStorage.add(route)
590 }
591
592 abstract getNextNode(
593 path: string,
594 pathIndex: number,
595 nodeStack: any,
596 paramsCount: number
597 ): Node | undefined
598}
599
600abstract class ParentNode extends NodeBase {
601 readonly staticChildren: Record<string, StaticNode> = Object.create(null)
602
603 findStaticMatchingChild(
604 path: string,
605 pathIndex: number
606 ): StaticNode | undefined {
607 const staticChild = this.staticChildren[path.charAt(pathIndex)]
608 if (
609 staticChild === undefined ||
610 !staticChild.matchPrefix(path, pathIndex)
611 ) {
612 return undefined
613 }
614 return staticChild
615 }
616
617 getStaticChild(path: string, pathIndex = 0): StaticNode | undefined {
618 if (path.length === pathIndex) {
619 return this as any
620 }
621
622 const staticChild = this.findStaticMatchingChild(path, pathIndex)
623 if (staticChild === undefined) {
624 return undefined
625 }
626
627 return staticChild.getStaticChild(
628 path,
629 pathIndex + staticChild.prefix.length
630 )
631 }
632
633 createStaticChild(path: string): StaticNode {
634 if (path.length === 0) {
635 return this as any
636 }
637
638 let staticChild = this.staticChildren[path.charAt(0)]
639 if (staticChild) {
640 let i = 1
641 for (; i < staticChild.prefix.length; i++) {
642 if (path.charCodeAt(i) !== staticChild.prefix.charCodeAt(i)) {
643 staticChild = staticChild.split(this, i)
644 break
645 }
646 }
647 return staticChild.createStaticChild(path.slice(i))
648 }
649
650 const label = path.charAt(0)
651 this.staticChildren[label] = new StaticNode(path)
652 return this.staticChildren[label]
653 }
654}
655
656class StaticNode extends ParentNode {
657 readonly _tag = "StaticNode"
658 constructor(prefix: string) {
659 super()
660 this.setPrefix(prefix)
661 }
662
663 prefix!: string
664 matchPrefix!: (path: string, pathIndex: number) => boolean
665 readonly parametricChildren: Array<ParametricNode> = []
666
667 wildcardChild: WildcardNode | undefined
668
669 private setPrefix(prefix: string) {
670 this.prefix = prefix
671
672 // Child selection already matched the first character.
673 if (prefix.length === 1) {
674 this.matchPrefix = (_path, _pathIndex) => true
675 } else {
676 const tail = prefix.slice(1)
677 this.matchPrefix = (path, pathIndex) => path.startsWith(tail, pathIndex + 1)
678 }
679 }
680
681 getParametricChild(regex: RegExp | undefined): ParametricNode | undefined {
682 if (regex === undefined) {
683 return this.parametricChildren.find((child) => child.isRegex === false)
684 }
685
686 const source = regex.source
687 return this.parametricChildren.find((child) => {
688 if (child.regex === undefined) {
689 return false
690 }
691 return child.regex.source === source
692 })
693 }
694
695 createParametricChild(
696 regex: RegExp | undefined,
697 staticSuffix: string | undefined,
698 nodePath: string
699 ) {
700 let child = this.getParametricChild(regex)
701 if (child !== undefined) {
702 child.nodePaths.add(nodePath)
703 return child
704 }
705
706 child = new ParametricNode(regex, staticSuffix, nodePath)
707 this.parametricChildren.push(child)
708 this.parametricChildren.sort((child1, child2) => {
709 if (!child1.isRegex) return 1
710 if (!child2.isRegex) return -1
711
712 if (child1.staticSuffix === undefined) return 1
713 if (child2.staticSuffix === undefined) return -1
714
715 if (child2.staticSuffix.endsWith(child1.staticSuffix)) return 1
716 if (child1.staticSuffix.endsWith(child2.staticSuffix)) return -1
717
718 return 0
719 })
720
721 return child
722 }
723
724 createWildcardChild() {
725 if (this.wildcardChild === undefined) {
726 this.wildcardChild = new WildcardNode()
727 }
728 return this.wildcardChild
729 }
730
731 split(parentNode: ParentNode, length: number) {
732 const parentPrefix = this.prefix.slice(0, length)
733 const childPrefix = this.prefix.slice(length)
734
735 this.setPrefix(childPrefix)
736
737 const staticNode = new StaticNode(parentPrefix)
738 staticNode.staticChildren[childPrefix.charAt(0)] = this
739 parentNode.staticChildren[parentPrefix.charAt(0)] = staticNode
740
741 return staticNode
742 }
743
744 getNextNode(
745 path: string,
746 pathIndex: number,
747 nodeStack: Array<BrotherNode>,
748 paramsCount: number
749 ): Node | undefined {
750 let node: Node | undefined = this.findStaticMatchingChild(path, pathIndex)
751 let parametricBrotherNodeIndex = 0
752
753 if (node === undefined) {
754 if (this.parametricChildren.length === 0) {
755 return this.wildcardChild
756 }
757
758 node = this.parametricChildren[0]
759 parametricBrotherNodeIndex = 1
760 }
761
762 if (this.wildcardChild !== undefined) {
763 nodeStack.push({
764 paramsCount,
765 brotherPathIndex: pathIndex,
766 brotherNode: this.wildcardChild
767 })
768 }
769
770 for (
771 let i = this.parametricChildren.length - 1;
772 i >= parametricBrotherNodeIndex;
773 i--
774 ) {
775 nodeStack.push({
776 paramsCount,
777 brotherPathIndex: pathIndex,
778 brotherNode: this.parametricChildren[i]
779 })
780 }
781
782 return node
783 }
784}
785
786class ParametricNode extends ParentNode {
787 readonly _tag = "ParametricNode"
788 readonly regex: RegExp | undefined
789 readonly staticSuffix: string | undefined
790 constructor(
791 regex: RegExp | undefined,
792 staticSuffix: string | undefined,
793 nodePath: string
794 ) {
795 super()
796 this.regex = regex
797 this.staticSuffix = staticSuffix
798 this.isRegex = !!regex
799 this.nodePaths = new Set([nodePath])
800 }
801
802 readonly isRegex: boolean
803 readonly nodePaths: Set<string>
804
805 getNextNode(path: string, pathIndex: number) {
806 return this.findStaticMatchingChild(path, pathIndex)
807 }
808}
809
810class WildcardNode extends NodeBase {
811 readonly _tag = "WildcardNode"
812 getNextNode(
813 _path: string,
814 _pathIndex: number,
815 _nodeStack: any,
816 _paramsCount: number
817 ): Node | undefined {
818 return undefined
819 }
820}
821
822// --
823
824interface Assert {
825 (condition: any, message?: string): asserts condition
826}
827const assert: Assert = (condition, message) => {
828 if (!condition) {
829 throw new Error(message)
830 }
831}
832
833function removeDuplicateSlashes(path: string): Router.PathInput {
834 if (path.indexOf("//") === -1) {
835 return path as Router.PathInput
836 }
837 return path.replace(/\/\/+/g, "/") as Router.PathInput
838}
839
840function trimLastSlash(path: string): Router.PathInput {
841 if (path.length > 1 && path.charCodeAt(path.length - 1) === 47) {
842 return path.slice(0, -1) as Router.PathInput
843 }
844 return path as Router.PathInput
845}
846
847function makeCreateParams(
848 params: ReadonlyArray<string>
849): (paramsArray: ReadonlyArray<string>) => Record<string, string> {
850 const len = params.length
851 if (len === 0) {
852 return () => Object.create(null)
853 }
854 return function(paramsArray) {
855 const paramsObject: Record<string, string> = Object.create(null)
856 for (let i = 0; i < len; i++) {
857 paramsObject[params[i]] = paramsArray[i]
858 }
859 return paramsObject
860 }
861}
862
863function getClosingParenthensePosition(path: string, idx: number) {
864 // `path.indexOf()` will always return the first position of the closing parenthese,
865 // but it's inefficient for grouped or wrong regexp expressions.
866 // see issues #62 and #63 for more info
867
868 let parentheses = 1
869
870 while (idx < path.length) {
871 idx++
872
873 // ignore skipped chars
874 if (path[idx] === "\\") {
875 idx++
876 continue
877 }
878
879 if (path[idx] === ")") {
880 parentheses--
881 } else if (path[idx] === "(") {
882 parentheses++
883 }
884
885 if (!parentheses) return idx
886 }
887
888 throw new TypeError("Invalid regexp expression in \"" + path + "\"")
889}
890
891function trimRegExpStartAndEnd(regexString: string) {
892 // removes chars that marks start "^" and end "$" of regexp
893 if (regexString.charCodeAt(1) === 94) {
894 regexString = regexString.slice(0, 1) + regexString.slice(2)
895 }
896
897 if (regexString.charCodeAt(regexString.length - 2) === 36) {
898 regexString = regexString.slice(0, regexString.length - 2) +
899 regexString.slice(regexString.length - 1)
900 }
901
902 return regexString
903}
904
905function escapeRegExp(string: string) {
906 return string.replace(/[.*+?^${}()|[\]\\]/g, "\\$&")
907}
908
909// It must spot all the chars where decodeURIComponent(x) !== decodeURI(x)
910// The chars are: # $ & + , / : ; = ? @
911function decodeComponentChar(highCharCode: number, lowCharCode: number) {
912 if (highCharCode === 50) {
913 if (lowCharCode === 53) return "%"
914
915 if (lowCharCode === 51) return "#"
916 if (lowCharCode === 52) return "$"
917 if (lowCharCode === 54) return "&"
918 if (lowCharCode === 66) return "+"
919 if (lowCharCode === 98) return "+"
920 if (lowCharCode === 67) return ","
921 if (lowCharCode === 99) return ","
922 if (lowCharCode === 70) return "/"
923 if (lowCharCode === 102) return "/"
924 return undefined
925 }
926 if (highCharCode === 51) {
927 if (lowCharCode === 65) return ":"
928 if (lowCharCode === 97) return ":"
929 if (lowCharCode === 66) return ";"
930 if (lowCharCode === 98) return ";"
931 if (lowCharCode === 68) return "="
932 if (lowCharCode === 100) return "="
933 if (lowCharCode === 70) return "?"
934 if (lowCharCode === 102) return "?"
935 return undefined
936 }
937 if (highCharCode === 52 && lowCharCode === 48) {
938 return "@"
939 }
940 return undefined
941}
942
943function safeDecodeURI(path: string) {
944 let shouldDecode = false
945 let shouldDecodeParam = false
946
947 let querystring = ""
948
949 for (let i = 1; i < path.length; i++) {
950 const charCode = path.charCodeAt(i)
951
952 if (charCode === 37) {
953 const highCharCode = path.charCodeAt(i + 1)
954 const lowCharCode = path.charCodeAt(i + 2)
955
956 if (decodeComponentChar(highCharCode, lowCharCode) === undefined) {
957 shouldDecode = true
958 } else {
959 shouldDecodeParam = true
960 // %25 - encoded % char. We need to encode one more time to prevent double decoding
961 if (highCharCode === 50 && lowCharCode === 53) {
962 shouldDecode = true
963 path = path.slice(0, i + 1) + "25" + path.slice(i + 1)
964 i += 2
965 }
966 i += 2
967 }
968 // Some systems do not follow RFC and separate the path and query
969 // string with a `;` character (code 59), e.g. `/foo;jsessionid=123456`.
970 // Thus, we need to split on `;` as well as `?` and `#`.
971 } else if (charCode === 63 || charCode === 59 || charCode === 35) {
972 querystring = path.slice(i + 1)
973 path = path.slice(0, i)
974 break
975 }
976 }
977 const decodedPath = shouldDecode ? decodeURI(path) : path
978 return { path: decodedPath, querystring, shouldDecodeParam } as const
979}
980
981function safeDecodeURIComponent(uriComponent: string) {
982 const startIndex = uriComponent.indexOf("%")
983 if (startIndex === -1) return uriComponent
984
985 let decoded = ""
986 let lastIndex = startIndex
987
988 for (let i = startIndex; i < uriComponent.length; i++) {
989 if (uriComponent.charCodeAt(i) === 37) {
990 if (i + 2 >= uriComponent.length) break
991
992 const highCharCode = uriComponent.charCodeAt(i + 1)
993 const lowCharCode = uriComponent.charCodeAt(i + 2)
994
995 const decodedChar = decodeComponentChar(highCharCode, lowCharCode)
996 decoded += uriComponent.slice(lastIndex, i) + decodedChar
997
998 lastIndex = i + 3
999 }
1000 }
1001 return (
1002 uriComponent.slice(0, startIndex) + decoded + uriComponent.slice(lastIndex)
1003 )
1004}
1005
1006const httpMethods = [
1007 "ACL",
1008 "BIND",
1009 "CHECKOUT",
1010 "CONNECT",
1011 "COPY",
1012 "DELETE",
1013 "GET",
1014 "HEAD",
1015 "LINK",
1016 "LOCK",
1017 "M-SEARCH",
1018 "MERGE",
1019 "MKACTIVITY",
1020 "MKCALENDAR",
1021 "MKCOL",
1022 "MOVE",
1023 "NOTIFY",
1024 "OPTIONS",
1025 "PATCH",
1026 "POST",
1027 "PROPFIND",
1028 "PROPPATCH",
1029 "PURGE",
1030 "PUT",
1031 "QUERY",
1032 "REBIND",
1033 "REPORT",
1034 "SEARCH",
1035 "SOURCE",
1036 "SUBSCRIBE",
1037 "TRACE",
1038 "UNBIND",
1039 "UNLINK",
1040 "UNLOCK",
1041 "UNSUBSCRIBE"
1042] as const