Hone logo
Hone
Problems

Type-Level Regex Engine in TypeScript

This challenge tasks you with building a type-level regular expression engine in TypeScript. The goal is to create a system where you can define regular expressions as types and then use these types to validate other string literal types. This allows for compile-time validation, catching potential errors before runtime.

Problem Description

Your task is to design and implement a set of TypeScript types that can parse and match simple regular expressions against string literal types. This engine should support basic regex constructs like literal characters, concatenation, the Kleene star (*), and optionally alternation (|) and character classes ([...]).

Key Requirements:

  1. Literal Matching: The engine must be able to match exact string literal types.
  2. Concatenation: Support for matching sequences of literal strings.
  3. Kleene Star (*): Implement the Kleene star operator, which matches zero or more occurrences of the preceding element.
  4. Optional: Ability to match an optional character or sequence.
  5. String Literal Input: The engine will operate on string literal types (e.g., "abc", "123").
  6. Result Type: A type that indicates whether a given string literal type matches the regex type. A common pattern is to return true for a match and false otherwise.

Optional but highly encouraged:

  1. Alternation (|): Support for matching either one pattern or another.
  2. Character Classes ([...]): Support for matching any single character from a defined set.

Expected Behavior:

Given a regex type and a string literal type, the engine should return true if the string literal matches the regex, and false otherwise. The matching should be greedy where applicable (e.g., with *).

Edge Cases:

  • Empty strings ("").
  • Regexes that match empty strings.
  • Regexes that match the empty string with *.
  • Complex combinations of operators.

Examples

Example 1: Simple Literal Match

// Regex: "hello"
type HelloRegex = Literal<"hello">;

// String to test: "hello"
type TestString1 = "hello";

// Expected Output: true
type Match1 = Match<TestString1, HelloRegex>;

Example 2: Concatenation

// Regex: "a" followed by "b"
type ABRegex = Concat<Literal<"a">, Literal<"b">>;

// String to test: "ab"
type TestString2 = "ab";

// Expected Output: true
type Match2 = Match<TestString2, ABRegex>;

// String to test: "ac"
type TestString3 = "ac";

// Expected Output: false
type Match3 = Match<TestString3, ABRegex>;

Example 3: Kleene Star (*)

// Regex: Zero or more 'a's
type StarARegex = Star<Literal<"a">>;

// String to test: ""
type TestString4 = "";

// Expected Output: true
type Match4 = Match<TestString4, StarARegex>;

// String to test: "aaa"
type TestString5 = "aaa";

// Expected Output: true
type Match5 = Match<TestString5, StarARegex>;

// String to test: "aab"
type TestString6 = "aab";

// Expected Output: false
type Match6 = Match<TestString6, StarARegex>;

Example 4: Alternation (|) (Optional)

// Regex: "cat" or "dog"
type CatOrDogRegex = Or<Literal<"cat">, Literal<"dog">>;

// String to test: "cat"
type TestString7 = "cat";

// Expected Output: true
type Match7 = Match<TestString7, CatOrDogRegex>;

// String to test: "dog"
type TestString8 = "dog";

// Expected Output: true
type Match8 = Match<TestString8, CatOrDogRegex>;

// String to test: "cow"
type TestString9 = "cow";

// Expected Output: false
type Match9 = Match<TestString9, CatOrDogRegex>;

Example 5: Character Class ([...]) (Optional)

// Regex: A digit (0-9)
type DigitRegex = CharClass<'0', '9'>;

// String to test: "5"
type TestString10 = "5";

// Expected Output: true
type Match10 = Match<TestString10, DigitRegex>;

// String to test: "a"
type TestString11 = "a";

// Expected Output: false
type Match11 = Match<TestString11, DigitRegex>;

Constraints

  • The implementation must be entirely within TypeScript's type system. No runtime JavaScript code should be used for the core matching logic.
  • The regex syntax will be defined by your type system (e.g., using specific type constructors like Literal, Concat, Star, Or, CharClass).
  • The matching process should be reasonably efficient within the TypeScript compiler. Avoid excessively deep type recursion or overly complex conditional types that could lead to compiler performance issues or stack overflows. Aim for solutions that are understandable and maintainable.
  • Input strings will be simple literal strings. Avoid special characters in input strings that are not intended as part of the regex syntax.

Notes

  • This challenge is a deep dive into advanced TypeScript features like conditional types, template literal types, and type-level programming.
  • Consider how you will represent the regex patterns themselves. You might create helper types for basic building blocks (like Literal<T extends string>) and then combine them.
  • The Match type will be the core of your engine, taking the input string type and the regex type and returning a boolean.
  • Think about how to handle the state of the matching process recursively.
  • For the * operator, you'll need to handle both matching zero occurrences and matching one or more.
  • For the optional features (| and [...]), ensure they integrate seamlessly with the existing operators.
Loading editor...
typescript