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 <[email protected]> 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

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.

Hi @sno2 , I've found a small bug in your type, but it's easy to fix:

type L = StringLength<string> // is set to 1 !! (it should be number if length is not known)

Fix:

export type StringLength<T extends string> = T extends ''
  ? 0
  : string extends T
    ? number
    : StringLengthUp<T>;

type L = StringLength<string> // is set to number

Moreover, if we want to make it work better with "tweaked types" (the result of complex type guards), we could refine it to be:

export type StringLength<T extends string> = T extends ''
  ? 0
  : string extends T
    ? number
    : number extends T['length'] // it checks if length is already statically known
      ? StringLengthUp<T>
      : T['length']

@sno2 For reference, I included a variant of your work in one of my libraries: https://www.npmjs.com/package/@coderspirit/nominal-inputs (and left the proper references to your gist 😃 )