Bug: Circular references not allowed for template literal types

[GuiltyDolphin]

Bug Report

🔎 Search Terms

• circularly, template literal

Related issues: #43335.

🕗 Version & Regression Information

• This changed between versions 4.0.5 and 4.1.5 (different bug before)

⏯ Playground Link

Playground link with relevant code

💻 Code

// you can have circular references in tuple types
type OneOrMoreArr0<C> = C | [C, ...OneOrMoreArr0<C>[]];
// note that
//
// type OneOrMoreArr0<C> = C | [C, OneOrMoreArr0<C>];
//
// is also valid
type OneOrMoreArr<C> = Exclude<OneOrMoreArr0<C>, C>;

const noEmptyArr: [] extends OneOrMoreArr<'*'> ? false : true = true;

const x1: OneOrMoreArr<'*'> = ['*'];
const x2: OneOrMoreArr<'*'> = ['*', '*'];
const x3: OneOrMoreArr<'*'> = ['*', '*', '*']

// but when you try and do the same thing with template literal types, you get an error
//
// "Type alias 'OneOrMoreStr0' circularly references itself."
//
// "Type 'OneOrMoreStr0' is not generic."
type OneOrMoreStr0<C extends string> = C | `${C}${OneOrMoreStr0<C>}`

// we should be able to do the above, and then have e.g.,
//
// const y1: OneOrMoreStr<'*'> = '*';
// const y2: OneOrMoreStr<'*'> = '**';
// const y3: OneOrMoreStr<'*'> = '***';


// if 'C' is the empty string, the above just reduces to:
//
// OneOrMoreStr0<''> = '';
//
// otherwise the same logic as with `OneOrMoreArr0` should apply

🙁 Actual behavior

You get the error:

    Type alias 'OneOrMoreStr0' circularly references itself.
    Type 'OneOrMoreStr0' is not generic.

🙂 Expected behavior

This should type check like with the tuple example - it's the same principle, just with template literals.

[andrewbranch]

it's the same principle, just with template literals

There’s a whole machinery for lazily normalizing tuples and representing their non-normalized forms. It seems quite likely to me that the analogous machinery doesn’t exist for template literal types and would be a lot of complexity to set up, but I’m not sure—pinging @ahejlsberg for a quick judgment of how impossible this sounds 😁

[tim-stasse]

There’s a whole machinery for lazily normalizing tuples and representing their non-normalized forms. It seems quite likely to me that the analogous machinery doesn’t exist for template literal types and would be a lot of complexity to set up, but I’m not sure—pinging @ahejlsberg for a quick judgment of how impossible this sounds 😁

Please correct me if I'm wrong, but I believe this would go a long way to solving the issue of exploding template literal types when using unions, no? i.e. stop producing the error: "Expression produces a union type that is too complex to represent" when trying to do something like below, or in this Playground.

type Numeric = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
type Alphabetic =
  | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm'
  | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'
type Alphanumeric = Alphabetic | Numeric

type Repeat<
    Char extends string,
    Count extends number,
    Joined extends string = ``,
    Acc extends 0[] = []
> = Acc['length'] extends Count ? Joined : Repeat<Char, Count, `${Joined}${Char}`, [0,...Acc]>

// Error: Expression produces a union type that is too complex to represent. (2590)
type UUIDV4 = `${Repeat<Alphanumeric, 8>}-${Repeat<Alphanumeric, 4>}-${Repeat<Alphanumeric, 4>}-${Repeat<Alphanumeric, 4>}-${Repeat<Alphanumeric, 12>}`

Of course this works when used for a smaller number of repeats (which is as designed — I believe the limit is 100,000 types in a single union, as per this comment on another issue):

// type Hex = "aaa" | "aab" | "aac" | "aad" | "aae" | "aaf" | "aag" | "aah" | "aai"
// | "aaj" | "aak" | "aal" | "aam" | "aan" | "aao" | "aap" | "aaq" | "aar" | "aas" | "aat"
// | "aau" | "aav" | "aaw" | ... 46632 more ... | "999"
type Hex = Repeat<Alphanumeric, 3>

But if instead of producing a union type and exploding, what if template literal types were lazily evaluated and produced something like:

// type UUIDV4 = `${Alphanumeric} ... 6 more ... ${Alphanumeric}-${Alphanumeric}
// ... 2 more ... ${Alphanumeric}-${Alphanumeric} ... 2 more ... ${Alphanumeric}-${Alphanumeric}
// ... 2 more ... ${Alphanumeric}-${Alphanumeric} ... 10 more ... ${Alphanumeric}`
type UUIDV4 = `${Repeat<Alphanumeric, 8>}-${Repeat<Alphanumeric, 4>}-${Repeat<Alphanumeric, 4>}-${Repeat<Alphanumeric, 4>}-${Repeat<Alphanumeric, 12>}`

@andrewbranch, is this pretty much the same thing you had in mind when you said it'd probably be too complex to add the necessary infrastructure to support?

[andrewbranch]

Yes 😄

[tim-stasse]

@andrewbranch Thanks. I'm [obviously] not an expert on the typescript compiler, but would you mind sharing why you think it might be a complex change? Is it because of technical debt; or an architectural issue or something? e.g. maybe it'd be too hard to reuse code from the existing recursive feature(s)? I'm mostly wondering out of professional curiosity more than anything! 😄

[andrewbranch]

I’m honestly not enough of an expert on how we deal with deferred recursive types to be 100% confident about how difficult this would be and what the biggest challenges would be, but I’m familiar enough to have an intuition that it would be complicated. Even if I were wrong about that, I think we’d want to see compelling use cases for why we should add this kind of complexity. Template literal types were created in large part to support mapped type as clauses, which have super compelling uses, like describing the relationship between an object like { foo: string } and { getFoo(): string, setFoo(foo: string): void }. I don’t think a super-fine-grained type-space string validator is as compelling as that, but that’s why issues like this one are Awaiting More Feedback.

[tim-stasse]

Thanks, that really helps to understand the thought process behind adding template literal types 👍🏼 I'm curious though, exactly which of the characteristics/traits of that relationship made it a compelling use case to the team? I mean it's obviously, without question, a very compelling reason 😄 but phrased another way, I guess my question is what goes into making the teams' decision-making process and/or how does the team actually measure/quantify how compelling one feature is/might be over another? 🙂

[GuiltyDolphin]

@andrewbranch For use cases, I can think of a couple off the top of my head:

1. Type safety for parsers. E.g., you might know that a heading starts with a number of # characters, so you could use recursive template literals to specify that the text matched fits that description. E.g., you might have a function oneOrMore<S extends string>(s: S): OneOrMore<S> | undefined

2. Complex mapped keys. You could use this to (potentially) build parameterised types from strings, e.g.,

interface ZTy {
  Number: number;
  String: string;
}

interface OT<T> {
  Array: Array<T>;
}

type ZType = keyof ZTy;
type OType = keyof OTy<any>;
type CType = ZType | `${OType}[${CType}]`;

type MapTy<C extends CType> = C extends ZType ? ZTy[C] :
    C extends `${infer OT}[${infer PT}]` ? OT extends OType ? PT extends CType ? OTy<MapTy<PT>>[OT]
    : never : never : never;

type StrArr = MapTy<"Array[String]">;
type NestedNumArr = MapTy<"Array[Array[Number]]">;

Which would be pretty cool. Specifically, it would allow you to better emulate partially-applied types.

[ahejlsberg]

Neither tuple types nor template literal types permit true recursion. We support rest elements in tuple types (the ...XXX[] syntax), which can be circular, allowing you to have repeated elements. But you can't have repeated patterns such as

type StrNumPairs = [] | [string, number, ...StrNumPairs];  // Error, circular

It certainly would be nice to allow that (in tuples as well as template literals), but it would add significant complexity. For example, we currently normalize tuple and template literal types, allowing us to share representation of structurally equivalent types. We'd only be able to partially do that for potentially recursive types. Also, code that processes tuple and template literal types, such as relationship checking, type inference, and type instantiation, would need lazy partial materialization and infinite recursion guards and limits. It's all possible, but it is complex and I'm not sure the slight added expressiveness merits that complexity.

[GuiltyDolphin]

@ahejlsberg Yeah, I'm always running into issues w/ recursion support. That said, I come from a dependent-types background so I might be pushing the type system too hard. I'd still +1 the idea, despite the complexities, but industry may feel differently.

[tim-stasse]

@ahejlsberg, thanks for the explanation; I appreciate it 🙂 Totally understand that code is cost. Every line you don't write is an improvement 😉 Would the code you'd need for lazy partial materialization and the infinite recursion guards not be generalizable enough to reuse elsewhere? Without any knowledge of the codebase myself, could you not refactor it to be used by other recursive types (including future ones that may not yet exist)? Could that not then theoretically reduce the overall complexity? 🤔 Just spitballing here; you and the team are obviously the experts 😄 (but you're also cursed with the expertise 😉)

[ericdrobinson]

A simple use case (for which I have several variations on the theme) in a codebase I'm working on involves the following:

const enum Moods
{
    Happy = "happy",
    Sad = "sad",
    Worried = "worried",
    //... some 50 more...
    Joyous = "joyous",
}

// Type alias 'MoodList' circularly references itself.ts(2456)
type MoodList = `${Moods}` | `${Moods}, ${MoodList}`;

interface SomeObject
{
    /** Comma separated list of well-known Mood values. */
    moods: MoodList;
}

At present I make do with moods: string and the doc comment, but the added type checks would be handy-dandy.

[lhwdev]

In my case, I'm giving HTTP headers specific types. For example, for allow header of HTTP "GET", "GET, POST, PUT", "PUT, POST" or "GET , POST" is permitted, but "GEEK, POUST, PUUT", "GET,, POST, PUT" or "PUT PATCH" is disallowed.
Converting to array is not feasible, as converting from/to array has runtime cost, and it cannot preserve some of original runtime string including how whitespaces are placed.

[gomain]

Many apis generate and consume comma delimited lists of known terms.

type Term = "term1" | "term2" | "term3";
const terms: ??? = "term1, term3";
function getTerms(): ??? {}
function takeTerms(terms: ???) {}

It would be real handy for

takeTerms(getTerms());

to type check.

[JesusTheHun]

Maybe explicitly marking something as unknown number of occurence would simplify the implementation significantly ?

// Simple, explicit keyword
type MyRecursivePath = `typescript.is${many '.super'}.cool`;

// Regex style (I personally don't like it but hey 🤷‍♂️)
type MyRecursivePath = `typescript.is${'.super'?}.cool`; // 0 or 1 repetition
type MyRecursivePath = `typescript.is${'.super'+}.cool`; // 1 or more repetition
type MyRecursivePath = `typescript.is${'.super'*}.cool`; // No idea how many repetition

// Array style
type MyRecursivePath = `typescript.is${'.super'[]}.cool`; // 0 or 1 repetition

So the definition is explicit and the description does not resolve anything, it spits out the declaration.
As for the type checking, because the repetition is declared explicitly, typescript eats up the same substring until it no longer matches and then move on.

Obviously I have very little knowledge of the compiler, but if the biggest burden is the resolving the circular reference, then explicit declaration would solve that part.

On a side note I would like to say that most people interested in this feature are probably library maintainers, so I would not expect a lot of feedbacks, but it would impact a lot of users.