A fast string length implementation in the TypeScript type system

fast-string-type-length.ts

/**
 * A logarithmic string length algorithm in the TypeScript type system utilizing
 * a memoizing recursive type. Computes the length of any string with far
 * superior performance than any other current implementations via a doubling
 * cache and string patterns backing the checks. Works for any string with less
 * than 10,000 characters due to the tuple size limits for the cache (in total).
 *
 * @author Carter Snook <cartersnook04@gmail.com> github.com/sno2
 * @license https://unlicense.org/ (credit would be nice tho)
 */

type TCache = [string, 0[]];

type StringLengthUp<
  T extends string,
  $Acc extends 0[] = [],
  $Cache extends TCache[] = [[`$${string}`, [0]]],
> =
  //
  $Cache extends [infer C extends TCache, ...infer $RestCache extends TCache[]]
    ? (
      `${C[0]}${C[0]}_` extends `$${string}$${infer $After}`
        ? `${C[0]}${$After}` extends `${infer $Before}_` ? $Before : never
        : never
    ) extends infer $DoubleC extends string
      ? `$${T}` extends `${$DoubleC}${infer $Rest}` ? StringLengthUp<
          $Rest,
          [...$Acc, ...C[1], ...C[1]],
          [[$DoubleC, [...C[1], ...C[1]]], ...$Cache]
        >
      : `$${T}` extends `${C[0]}${infer $Rest}`
        ? StringLengthUp<$Rest, [...$Acc, ...C[1]], $Cache>
      : StringLengthDown<T, $Acc, $RestCache>
    : never
    : $Acc["length"];

type StringLengthDown<
  T extends string,
  $Acc extends 0[],
  $Cache extends TCache[],
> = $Cache extends
  [infer C extends TCache, ...infer $RestCache extends TCache[]]
  ? `$${T}` extends `${C[0]}${infer $Rest}`
    ? StringLengthDown<$Rest, [...$Acc, ...C[1]], $Cache>
  : StringLengthDown<T, $Acc, $RestCache>
  : $Acc["length"];

type StringLength<T extends string> = T extends "" ? 0 : StringLengthUp<T>;

type String9999 = "<a 9999 character long string>";
type String9999Length = StringLength<String9999>; // 9999

TypeScript Playground Link

cc @sindresorhus @millsp Might be interested?

Impressive work, and way out of my league--can this be used somehow to type lower and/or upper length bounds to a string?

Impressive work, and way out of my league--can this be used somehow to type lower and/or upper length bounds to a string?

Hmm interesting idea. You could use it for having a static string type for the minimum length of a string. You could also define a maximum but you would just use the minimum static string type to check if it is above the max. This would require generics with weird parameter asserts, though.