[TS 4.1] Type-level String Accumulation Error In Recursive Type

[harrysolovay]

TypeScript Version: 4.1.0-dev.20201014

Search Terms: recursive, type, string, literal, accumulation, reducer, token, split

I'm trying to create a mini type-level lexer, that deals solely with a sequence of GraphQL directives. Aka., the following are all valid:

@aaa

@bbb(some: "arg")

@ccc(some: "arg", and: "another")

@aaa @bbb(some: "arg") @ccc(some: "arg", and: "another")

Taking the last example, here's the type-level structure that I'm trying to compute.

{
    kind: never;
    value: "";
    next: {
        kind: "DIRECTIVE";
        value: "aaa ";
        next: {
            kind: "DIRECTIVE";
            value: "bbb";
            next: {
                kind: "ARGUMENT_START";
                value: "some: \"arg\"";
                next: {
                    kind: "ARGUMENT_END";
                    value: " ";
                    next: {
                        kind: "DIRECTIVE";
                        value: "ccc";
                        next: {
                          kind: "ARGUMENT_START";
                          value: "some: \"arg\", and: \"another\"";
                          next: undefined;
                        };
                    };
                };
            };
        };
    };
}

The generic type should be able to build such a structure––without provoking the excessive depth error––via tail calls.

Code

First we define the token type, along with a widened type, Token.Any (for the constraint of Next).

interface Token<
  Kind extends string,
  Value extends string,
  Next extends Token.Any | undefined
> {
  kind: Kind;
  value: Value;
  next: Next;
}

namespace Token {
  export type Any = Token<string, string, Token.Any | undefined, any>;
}

Next we define our recursive type.

type Tokenize<
  Src extends string,
  KindByDelimiter extends Record<string, string>,
  Acc extends string = "",
  LastDelimiter extends keyof KindByDelimiter = never
> =
  Src extends `${infer C0}${infer CRest}`
    ? C0 extends keyof KindByDelimiter
      ? Token<
          KindByDelimiter[LastDelimiter],
          Acc,
          Tokenize<CRest, KindByDelimiter, "", C0>
        >
      : Tokenize<CRest, KindByDelimiter, `${Acc}${C0}`, LastDelimiter>
    : undefined;

This Tokenize type checks whether the character at position 0 of Src is a subtype of a delimiting character (keyof KindByDelimiter). If so, then we've hit the start of the next token. Therefore we create a token with the kind name and accumulator, and then tail-call Tokenize with C0 as the new LastDelimiter. In the case that C0 is not a delimiting char, we progress down the string (adding C0 to the accumulator (Acc), passing CRest in as Src, and leaving LastDelimiter as is). If we've hit an empty string, we return undefined.

Result:

The final argument sequence does not evaluate to the expected token. Instead, we get any. I could well be missing something (in which case I apologies for an issue better suited for StackOverflow)... although I believe this to be a bug.

Here is the playground Link

Any suggestions as to a better approach would be greatly appreciated, although I understand you likely have higher priorities. Thank you!

[jcalz]

It might be helpful to pare this down to a more minimal reproduction so that extraneous details don't distract from the underlying issue. For example:

type IterateNoOp<T extends string> =
  T extends `${infer C0}${infer CRest}` ? `${C0}${IterateNoOp<CRest>}` : "";
type Wrapped<T extends string> = { wrapped: IterateNoOp<T> };

type NotTooLong = "abcdefghij";
type Fine = IterateNoOp<NotTooLong>; // type Fine = "abcdefghij"
type AlsoFine = Wrapped<NotTooLong> // type AlsoFine = { wrapped: "abcdefghij"; } 

type TooLong = "abcdefghijklmnopqrstuvwxyz";

type Err = IterateNoOp<TooLong>; // error!
// ------> ~~~~~~~~~~~~~~~~~~~~
// Type instantiation is excessively deep and possibly infinite
// type Err = `abcdefghijklmnopqrstuvwx${any}${any}`

type NoErr = Wrapped<TooLong>; // no error, but still:
// type NoErr = { wrapped: `abcdefghijklmnopqrstuvwx${any}${any}`; }

Playground link

Here all IterateNoOp does is return the same string you pass in, but it does it by recursively iterating over each character in the string. There is a rather shallow recursion limit, which the 26-character TooLong hits. If you try to use IterateNoOp directly on TooLong, you get a recursion limit error, and you can see that the actual type of Err gets those "I give up" any types from the compiler. When you use IterateNoOp indirectly by wrapping it, this apparently does not cause the compiler error, but the types are evaluated the same way.

---

The TS4.1 template literal stuff does tend to slam into recursion limits really easily, so hopefully there will be some way to address this soon.

Relevant issues:

• Template literal types and mapped type 'as' clauses #40336 implements template literals, and this comment says that hitting recursion limits when iterating character-by-character is "an orthogonal issue I'm still thinking about".

• Max depth limit does not trigger. Gives up and resolves type to any #32707 mentions the inconsistency where the "excessively deep" error does not show up even when it probably should.

[harrysolovay]

@jcalz thank you for this spectacular explanation and references. You're always incredibly helpful & I appreciate you!

[tjjfvi]

You can circumvent this by using HKTs.

type Access<T, U> = T[Extract<U, keyof T>]

interface GeneratorHKT<I, O> {
  _I: I,
  _O: O,
  input: I,
  _next: IteratorResult<I, O>
  next: IteratorResult<I, O>,
}

type CallGenHKT<G extends GeneratorHKT<any, any>, I extends G["_I"]> = (G & {input: I})["next"];
type IterateGenHKT<G extends GeneratorHKT<any, any>, N extends any> = N extends { done: true } ? N : CallGenHKT<G, Access<N, "value">>;

// Does 10 iterations
interface CompileGeneratorHKT10<G extends GeneratorHKT<any, any>> extends GeneratorHKT<G["_I"], G["_O"]> {
  next: IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IterateGenHKT<G, IteratorYieldResult<this["input"]>>>>>>>>>>>,
}

// Does 1000 iterations
interface CompileGeneratorHKT1000<G extends GeneratorHKT<any, any>> extends CompileGeneratorHKT10<CompileGeneratorHKT10<CompileGeneratorHKT10<G>>> {

}

interface IterateNoOpGenHKT extends GeneratorHKT<[acc: string, i: string], string> {
  next: (
    this["input"][1] extends `${infer C0}${infer CRest}`
      ? IteratorYieldResult<[`${this["input"][0]}${C0}`, CRest]>
      : IteratorReturnResult<this["input"][0]>
  )
}

// If we use normal property accessing (`A[B]`), it needs to check that `B` is assignable to `keyof A`,
// which causes excessively deep. Instead, we use `Access<A, B>`, which circumvents this.
// Strangely, if we make this alias generic intead of assuming `IterateNoOpGenHKT`, it
// throws excessively deep. I am unsure what the cause of this is, but I assume it is related.
type IterateNoOp<T extends string> = Access<IterateGenHKT<CompileGeneratorHKT1000<IterateNoOpGenHKT>, { done: false, value: ["", T] }>, "value">;

type NotTooLong = "abcdefghij";
type Fine = IterateNoOp<NotTooLong>;
// type Fine = "abcdefghij"

type LongerButStillFine = "abcdefghijklmnopqrstuvwxyz";
type StillFine = IterateNoOp<LongerButStillFine>;
// type StillFine = "abcdefghijklmnopqrstuvwxyz"

type SuperLong = "999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars 999 chars"
type StllStillFine = IterateNoOp<SuperLong>;
// type StillStillFine = "999 chars 999 chars..."

Playground Link

I was unable to get above 1000 with simple tweaks.