The Matching Engine Explained

Relevant source files

The following files were used as context for generating this wiki page:

• src/utils/matcher.ts
• test/matcher.test.ts
• src/utils/validation.ts
• README.md
• src/admin-html.ts
• SECURITY.md
• src/index.ts

The Matching Engine is the core component of gr8hopper, responsible for interpreting incoming request URLs and matching them against user-defined route patterns. It enables flexible, parameter-driven routing by parsing path segments and query parameters, extracting their values, and determining the correct redirect rule to apply. This system is designed to be both powerful, supporting wildcards and optional parameters, and performant, utilizing memoization for pattern parsing.

The engine's primary function is matchRoute, which takes a pattern, a request path, and query parameters, and returns a collection of extracted parameter values if a match is found, or null otherwise. The logic is self-contained within the application and is a key differentiator, allowing for complex redirect scenarios beyond simple URL shortening.

Sources: src/utils/matcher.ts:420-427, README.md:12-16

Core Matching Flow

The matching process is orchestrated by the matchRoute function. It follows a clear, sequential process to determine if an incoming request matches a given pattern.

This diagram illustrates the high-level logic flow within the matchRoute function.

1. Parse Pattern: The raw pattern string is first processed by parsePattern to separate it into path and query components. This result is cached to improve performance on subsequent requests for the same pattern.
2. Normalize: Both the pattern's path and the request's path are normalized by removing leading and trailing slashes. The request path is also converted to lowercase for case-insensitive matching.
3. Match Path: The engine attempts to match the path segments using the matchPathSegments function. This recursive function handles various syntax like named parameters, wildcards, and optional segments.
4. Full Consumption Check: If the path matches, the engine verifies that all segments of the incoming request path were consumed by the pattern. This prevents a pattern like a/**/c from incorrectly matching a path like a/b/c/d.
5. Match Query: Finally, matchQueryParams checks the request's query parameters against the query specifications defined in the pattern.
6. Return Result: If all steps succeed, an object containing all extracted parameters (from both path and query) is returned. Otherwise, null is returned, indicating no match.

Sources: src/utils/matcher.ts:420-471, test/matcher.test.ts:114-120

Pattern Parsing and Caching

At the heart of the matching engine is the parsePattern function, which deconstructs a route ID string into a structured ParsedPattern object. This object contains the pathPattern and an array of querySpecs that define the requirements for the query string.

To optimize performance, the results of parsePattern are stored in a memoization cache (parsePatternCache). This avoids the cost of re-parsing the same pattern string on every request. The cache has a maximum size and uses a simple LRU (Least Recently Used) eviction strategy.

Sources: src/utils/matcher.ts:19-27, 34-40

This diagram shows the caching mechanism for pattern parsing.

Parsed Data Structures

The parsePattern function produces a ParsedPattern object with the following structure:

interface ParsedPattern {
  pathPattern: string;
  querySpecs: QueryParamSpec[];
  hasQueryWildcard: boolean;
}

• pathPattern: The part of the pattern before the ?.
• querySpecs: An array of objects detailing each expected query parameter.
• hasQueryWildcard: A boolean indicating if a general query wildcard (?*) is present.

Each element in querySpecs is a QueryParamSpec:

interface QueryParamSpec {
  name: string;
  required: boolean;
  defaultValue?: string;
  isWildcard?: boolean;
  outputName?: string;
  literalValue?: string;
}

Sources: src/utils/matcher.ts:5-17

Path Matching

Path matching is performed by the matchPathSegments function, which recursively compares segments from the pattern against segments from the request path.

Path Matching Logic

• Case-Insensitive: Path matching is case-insensitive. A pattern Shop/{id} will match /shop/123 and /SHOP/123.
• Parameter Preservation: Captured parameter values, however, preserve their original casing from the request URL.
• Recursive Matching: A visit function inside matchPathSegments traverses the pattern and path, handling complex logic for optional segments and wildcards.

Sources: README.md:126-129, src/utils/matcher.ts:210-213, 298-301, test/matcher.test.ts:54-58

Supported Path Syntax

The engine supports a rich syntax for defining path patterns.

Syntax	Example	Description	Source
Literal	shop/about	Matches the exact path.	test/matcher.test.ts
Named Param	{id} or :id	Captures a single path segment into a parameter.	README.md:115, src/utils/matcher.ts:333-352
Optional Param	{id?} or :id?	Matches an optional path segment.	README.md:115, src/utils/matcher.ts:353-372
Default Value	{year=2024}	An optional segment that defaults to a value if not present.	README.md:115, src/utils/matcher.ts:380-385
Wildcard	*	Matches exactly one path segment.	README.md:116, src/utils/matcher.ts:285-296
Globstar	**	Matches zero or more path segments. Must be the last part of a pattern or followed by other segments.	README.md:116, src/utils/matcher.ts:257-283

Multiple Wildcards

If a pattern contains multiple wildcards of the same type (* or **), they are indexed to avoid name collisions in the captured parameters.

• First * is captured as *. Second is *1, third is *2, and so on.
• First ** is captured as **. Second is **1, etc.

Example:

• Pattern: a/*/b/*
• Path: a/x/b/y
• Captured Params: { "*": "x", "*1": "y" }

Sources: README.md:132-139, src/utils/matcher.ts:220-231, test/matcher.test.ts:122-131

Query Parameter Matching

After a successful path match, the matchQueryParams function validates the request's URLSearchParams.

Query Matching Logic

• Case-Sensitive: Unlike path matching, query parameter names are case-sensitive. A pattern ?source={source} will not match a URL with ?Source=google.
• Value Preservation: Parameter values are captured with their original casing.

Sources: README.md:126, 130, test/matcher.test.ts:155-164

Supported Query Syntax

The query string part of a pattern (after the ?) also has a specific syntax.

Syntax	Example	Description	Source
Required Param	?lang={lang}	The lang query parameter must be present.	src/utils/matcher.ts:160-165
Optional Param	?lang={lang?}	The lang query parameter is optional.	src/utils/matcher.ts:154-159
Default Value	?lang={lang=en}	If lang is missing, its value defaults to en.	src/utils/matcher.ts:145-152
Literal Value	?lang=en	The lang parameter must be present and its value must be exactly en.	src/utils/matcher.ts:167-173, test/matcher.test.ts:40-47
Wildcard Value	?utm=*	The utm parameter is optional and can have any value.	src/utils/matcher.ts:138-141
Query Wildcard	?*	Allows any and all query parameters to be present. They are all captured.	src/utils/matcher.ts:88-91, test/matcher.test.ts:34-38

Advanced Features and Edge Cases

Reserved {route} Placeholder

The placeholder {route} is reserved. It is automatically populated with the route's ID (the full pattern string), URL-encoded for safety. This is useful for tracking and analytics. Any user-defined parameter named route will be overwritten.

Sources: README.md:100, 131, src/utils/matcher.ts:305-308, 452-453

Parameter Name Extraction

The function getPatternParamNames is a utility that extracts all declared parameter names from a pattern string, including path parameters, query parameters, and the reserved route parameter. This is used to implement features like "Query Parameter Passthrough" by identifying which parameters are explicitly part of the route definition and should be excluded from passthrough.

Sources: src/utils/matcher.ts:429-471

Security: ReDoS Protection

The matching engine is designed to be resilient against Regular Expression Denial of Service (ReDoS) attacks. Complex patterns with multiple globstars (**) can lead to "catastrophic backtracking" if no match is found.

To mitigate this, the recursive visit function in matchPathSegments includes a backtracking limit, defined by the MAX_BACKTRACK_DEPTH constant. If a pattern match exceeds this depth, the process is aborted, and a warning is logged. This ensures that even a malicious or poorly constructed pattern cannot cause the server to hang.

Sources: src/utils/matcher.ts:20, 245-249, SECURITY.md:65-67, test/matcher.test.ts:143-153

Pattern Validation

Before a route pattern is saved, it is validated by validateRouteIdPattern in src/utils/validation.ts. This preemptive check ensures the structural integrity of the pattern, preventing runtime errors.

Validation checks include:

• The route ID is not empty.
• Braces ({}) are properly balanced and not nested.
• Path parameter placeholders ({name}, :name) have non-empty names.
• Query string specifications are well-formed.

This ensures that only valid and parsable patterns are stored and processed by the matching engine.

Sources: src/utils/validation.ts:28-70

Conclusion

The gr8hopper Matching Engine is a sophisticated system that provides the foundation for the application's powerful redirection capabilities. By combining a flexible pattern syntax, performant parsing with caching, and built-in security measures like ReDoS protection, it allows users to define both simple and highly complex routing rules with confidence. Its clear separation of path and query matching logic, along with support for various wildcards and parameter types, makes it a robust and central feature of the project.