Type-level accumulation produces 2589 unless as a linked list

[harrysolovay]

TypeScript Version: 4.1.0-dev.20201026

Search Terms: type-level, recursion, accumulator, intersection, linked list, tail, call

I've been struggling to find recursion limiter workarounds, and it's keeping me from representing something which I believe would be extremely useful: a GraphQL-source-string-to-TS-type utility type.

Code

We begin by defining our GraphQL statement delimiters.

type Delimiters = "enum" | "extend" | "input" | "interface" | "scalar" | "schema" | "type" | "union";

Next, we create a utility, which accepts a string and a union of possible substrings (our union of delimiters), and matches the first occurrence, along with its leading and trailing text.

export type MatchLeading<Src extends string, Delimiter extends string> =
  Src extends `${infer Leading}${Delimiter}${infer _Rest}` ? Leading : never;

export interface Match<
  Leading extends string,
  Delimiter extends string,
  Trailing extends string
> {
  leading: Leading;
  delimiter: Delimiter;
  trailing: Trailing;
}

export namespace Match {
  export type Any = Match<string, string, string>;

  type Values<X> = X[keyof X];

  export type First<
    Src extends string,
    DelimiterU extends string
  > = Values<{
    [Leader in MatchLeading<Src, DelimiterU>]: MatchLeading<Src, DelimiterU> extends `${Leader}${infer _Rest}`
      ? Src extends `${Leader}${infer DelimiterAndTrailing}`
        ? DelimiterAndTrailing extends `${DelimiterU}${infer Trailing}`
          ? DelimiterAndTrailing extends `${infer Delimiter}${Trailing}`
            ? Match<Leader, Delimiter, Trailing>
            : never
          : never
        : never
      : never;
  }>;
}

Here's an example of this utility's usage:

type X = FirstMatch<"a b c", "a" | "b" | "c">;

/**
 * ```ts
 * Match<"", "a", " b c">
 * ```
 *
 * –– or ––
 *
 * ```ts
 * {
 *   leading: "";
 *   match: "a";
 *   trailing: " b c";
 * }
 * ```
 */

Next, we begin creating our top-level generic Parse type, which accepts the GraphQL schema source string type and iterates over it using Match.First.

For the purposes of this issue, we won't be going into the mapping of the types. This is solely meant to demonstrate how we fail to iterate over the string while accumulating a record. In the final, implementation this record would contain the schema-corresponding types. For now though, we'll just build up a lookup of Match results, keyed by the leading text (Matched["leading"]).

type Parse<
  Src extends string,
  Matched extends Match<string, SchemaDelimiters, string> = Match.First<Src, SchemaDelimiters>
> =
  [Matched] extends [Match<string, SchemaDelimiters, string>]
    ? Record<Matched["leading"], Matched> & Parse<Matched["trailing"]>
    : {};

While the above fails with 2589, one subtle change lets it succeed:

type Parse_LinkedList<
  Src extends string,
  Matched extends Match<string, SchemaDelimiters, string> = Match.First<Src, SchemaDelimiters>
> =
  [Matched] extends [Match<string, SchemaDelimiters, string>]
-   ? Record<Matched["leading"], Matched> & Parse<Matched["trailing"]>
+   ? Record<Matched["leading"], Matched> & {next: Parse_LinkedList<Matched["trailing"]>}
    : {};

My first thought was to attach an accumulator, to which we could later traverse.

type Parse<
  Src extends string,
  Acc extends object = {},
  Matched extends Match<string, SchemaDelimiters, string> = Match.First<Src, SchemaDelimiters>
> =
  [Matched] extends [Match<string, SchemaDelimiters, string>]
    ? {acc: Acc & Record<Matched["leading"], Matched>; next: Parse<Matched["trailing"], Acc & Record<Matched["leading"], Matched>>}
    : {};

type Parsed = Parse<"" /* gql src string here */>;

type GetAcc<T extends object> = T extends {next: object} ? GetAcc<T["next"]> : T extends {acc: any} ? T["acc"] : never;

type Acc = GetAcc<Parsed>; // error

Surely enough, this gives us 2589 again––not on the usage of the Parsed type, but on its traversal.

I've tried many variations of this to see if I can get around the recursion limiting, but I'm unsuccessful every time. There doesn't seem to be a way to access the final acc.

When it comes to iterating over GraphQL schemas, these kinds of recursion limits are debilitating. If we are to create a future of greater type-system interoperability, robust type-level accumulation is a must.

Playground Link

[RyanCavanaugh]

If we are to create a future of greater type-system interoperability, robust type-level accumulation is a must.

The intent of template literals is not to use them to write parsers using the type system. I can't stress this enough; I know everyone was doing it for fun in various issues and on twitter, but this is not what they're for and we're not going to expend engineering effort to enable this scenario. Transforms like this should happen out-of-band in processing steps once when the GraphQL changes; by doing this in the type system you're redoing this work literally on every keystroke.

[harrysolovay]

Perhaps I misunderstand, but are the types not incrementally computed? Aka., it's fine if the gql types are recomputed when the schema source string changes... but it should not need recomputing when changes are made elsewhere in your code (?).

While I understand why this is not a priority, I'm still uncertain about why moving parsing into TypeScript––as to unify the environments––would be undesirable. To me it feels like a natural step. I'd love to know why you feel like this would be a mistake.

[RyanCavanaugh]

Parsing artifacts like ASTs are preserved (and even partially re-used if edited where possible) between edits, but semantic information produced from type computation is recomputed fresh on each edit.

Moving parsing (for the sake of generating .d.ts) into the TypeScript pipeline is perhaps a thing we will consider eventually, but that isn't what template literals is for and it isn't designed to support that level of modification. It's for trivial transforms like foo -> getFoo.

[harrysolovay]

I can't even imagine what would go into producing semantic information incrementally... would this change even make sense in the long-term?

With the parser-combinator-esque look of conditional assignability, I'm surprised that type-level parsers (via template literals) wouldn't be the preferred mechanism. Would extracting DSL types from strings be wrong for any reason other than performance?

[RyanCavanaugh]

Incremental semantic analysis is what flow is trying to do and... they're not really able to do much else except making that work 🙂. It's a big trade-off.

Parsing with template literals is fine from a correctness perspective, but you're going to encounter a lot of performance issues doing this on too many large strings, and various depth limiters are subject to change from version to version as we try to stop runaway or useless recursion in other scenarios. If we ever make something that's specifically for turning external DSLs into something TS understands, we'll make it very clear that that's what it's for.

[harrysolovay]

Thank you for these wonderful explanations Ryan!

[harrysolovay]

@RyanCavanaugh one last thought. Perhaps when DSL processing becomes a priority, it could still occur through template literals, but be safeguarded from unnecessary re-processing with an intrinsic utility type that the compiler recognizes as expensive, and treats differently.

import {ParseGraphQLSchema} from "wherever";
import {schema} from "./schema";

type Parsed = Expensive<ParseGraphQLSchema<typeof schema>>;

[tjjfvi]

I find it very surprising that types are not cached at all.

While adding that for all types might be unreliable and unwarranted at the moment, I think some sort of marker for expensive types like @harrysolovay suggested would be a good idea; #41263.

Additionally, in trying to solve the issue with GetAcc, I noticed that it seems that Parsed_LinkedListAcc has infinite depth:

type Assert<A, B extends A> = B;
type T = Assert<Parsed_LinkedListAcc, Parsed_LinkedListAcc["next"]>;

Playground Link

[tjjfvi]

Looking at it further, this makes sense:

type Parse_LinkedListAcc<
  Src extends string,
  Acc extends object = {},
  Matched extends Match<string, SchemaDelimiters, string> = Match.First<Src, SchemaDelimiters>
> =
  [Matched] extends [Match<string, SchemaDelimiters, string>]
    ? {acc: Acc & Record<Matched["leading"], Matched>; next: Parse_LinkedListAcc<Matched["trailing"], Acc & Record<Matched["leading"], Matched>>}
    : {};

You're checking if Matched (which is constrained to Match<string, SchemaDelimeters, string>) is assignable to Match<string, SchemaDelimiters, string>. I think you're trying to determine if Matched is never; to do that, you can use [Matched] extends ["__never__"] ? {} : ....

If I understand correctly, it should/could be written:

type Parse_LinkedListAcc<
  Src extends string,
  Acc extends object = {},
  Matched extends Match<string, SchemaDelimiters, string> = Match.First<Src, SchemaDelimiters>
> =
  [Matched] extends ["__never__"]
    ? null
    : {acc: Acc & Record<Matched["leading"], Matched>; next: Parse_LinkedListAcc<Matched["trailing"], Acc & Record<Matched["leading"], Matched>>};

Which works (read: doesn't throw 2589).

Applying this same thing to your first iteration, we get:

type Parse<
  Src extends string,
  Matched extends Match<string, SchemaDelimiters, string> = Match.First<Src, SchemaDelimiters>
> =
  [Matched] extends ["__never__"]
    ? {}
    : Record<Matched["leading"], Matched> & Parse<Matched["trailing"]>;

Which also works.

I suspect the reason the linked list fixed the 2589 was that typescript was deferring the infinite instantiation.

I suspect this Parse type will fail at (is the max depth 50?) delimiters (though I did not test this); that can be worked around via HKTs.

[tjjfvi]

A generic type-level parser I've been playing around with: Playground Link

It runs into 2589 very quickly.

[harrysolovay]

That's an interesting approach! Unfortunately––per Ryan's feedback––I don't think type-level parsers will be feasible in the near future :/

Especially considering large ASTs, such as that of GitHub's GraphQL API schema (parsed from ^30K loc).

I suppose we could file an issue to track the progression of a workflow tool for declaration generation. That might be the right move...

Although it doesn't feel as clean as would using template literals within the single environment. Hopefully this will become a possibility.