TypeScript の型のみで実装した簡易的な正規表現エンジン

simple-type-regexp.ts

type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y
  ? 1
  : 2
  ? true
  : false;

type And<A extends boolean, B extends boolean> = A extends true
  ? B extends true
    ? true
    : false
  : false;

type Or<A extends boolean, B extends boolean> = A extends true
  ? true
  : B extends true
  ? true
  : false;

type Head<T extends string> = T extends `${infer H}${infer _}` ? H : "";

type Rest<T extends string> = T extends `${infer _}${infer R}` ? R : "";

type Concat<T extends string, U extends string> = `${T}${U}`;

type MatchOne<Pattern extends string, Text extends string> = Pattern extends ""
  ? true
  : Text extends ""
  ? false
  : Pattern extends "."
  ? true
  : Pattern extends Text
  ? true
  : false;

type MatchQuestion<Pattern extends string, Text extends string> = Or<
  Match<Rest<Rest<Pattern>>, Text>,
  And<
    MatchOne<Head<Pattern>, Head<Text>>,
    Match<Rest<Rest<Pattern>>, Rest<Text>>
  >
>;

type MatchStar<Pattern extends string, Text extends string> = Or<
  Match<Rest<Rest<Pattern>>, Text>,
  And<
    MatchOne<Head<Pattern>, Head<Text>>,
    Head<Text> extends "" ? true : MatchStar<Pattern, Rest<Text>>
  >
>;

type MatchInternal<Pattern extends string, Text extends string> = Head<
  Rest<Pattern>
> extends "?"
  ? MatchQuestion<Pattern, Text>
  : Head<Rest<Pattern>> extends "*"
  ? MatchStar<Pattern, Text>
  : And<MatchOne<Head<Pattern>, Head<Text>>, Match<Rest<Pattern>, Rest<Text>>>;

type Match<Pattern extends string, Text extends string> = Pattern extends ""
  ? true
  : Pattern extends "$"
  ? Text extends ""
    ? true
    : MatchInternal<Pattern, Text>
  : MatchInternal<Pattern, Text>;

type Regexp<
  Pattern extends string,
  Text extends string
> = Head<Pattern> extends "^"
  ? Match<Rest<Pattern>, Text>
  : Match<Concat<".*", Pattern>, Text>;

function assert<T extends true>(): void {}

assert<Equal<MatchOne<"a", "a">, true>>();
assert<Equal<MatchOne<"a", "b">, false>>();
assert<Equal<MatchOne<".", "a">, true>>();
assert<Equal<MatchOne<"a", "">, false>>();

assert<Equal<MatchQuestion<"a?b", "b">, true>>();
assert<Equal<MatchQuestion<"a?b", "ab">, true>>();
assert<Equal<MatchQuestion<"a?b", "a">, false>>();

assert<Equal<Match<"abc", "abc">, true>>();
assert<Equal<Match<"abc", "abd">, false>>();
assert<Equal<Match<"a.c", "abc">, true>>();
assert<Equal<Match<"a.c", "abd">, false>>();
assert<Equal<Match<"abc$", "abc">, true>>();
assert<Equal<Match<"abc$", "abcd">, false>>();
assert<Equal<Match<"ab?c", "abc">, true>>();
assert<Equal<Match<"ab?c", "ac">, true>>();
assert<Equal<Match<"a*b", "b">, true>>();
assert<Equal<Match<"a*b", "ab">, true>>();
assert<Equal<Match<"a*b", "aab">, true>>();
assert<Equal<Match<"a*bc", "aaab">, false>>();

assert<Equal<Regexp<"abc", "abc">, true>>();
assert<Equal<Regexp<"abc", "abd">, false>>();
assert<Equal<Regexp<"^abc", "abc">, true>>();
assert<Equal<Regexp<"bc", "abcd">, true>>();
assert<Equal<Regexp<"cd", "abc">, false>>();
assert<Equal<Regexp<"abc$", "abc">, true>>();
assert<Equal<Regexp<"abc$", "abcd">, false>>();
assert<Equal<Regexp<".*abc", "abc">, true>>();
assert<Equal<Regexp<".*abc", "deadbeafabc">, true>>();

// A は true に評価される
type A = Regexp<"^a?b?c?$", "abc">;

// B は true に評価される
type B = Regexp<"abc*d?.*", "abcde">;

// C は false に評価される
type C = Regexp<".?ab*cc", "aabcbc">;