Template literal union type-checking is exponentially slower when type is explicitly annotated vs inferred

[LangLangBart]

🔎 Search Terms

"typeMaybeAssignableTo", "getAssignmentReducedType",
"getAssignmentReducedTypeWorker", "template literal union type-checking
performance", "filterType big union", "flow-based narrowing large template literal union"

🕗 Version & Regression Information

• Reproduces on TS 5,6,7 (did not test version 4 and below)

⏯ Playground Link

https://github.com/LangLangBart/ts-repro-union

💻 Code

(see the reproduction repo linked above)

I have the repro.ts and a TypeName.d.ts with a 40k string literals

// repro.ts
new class {
  private map: Record<string, TypeName[]> = { x: ['f_0|i_0'] }

  constructor() {
    let item: TypeName | undefined
    if (this.map.x) {
      const [entry] = this.map.x
      item = entry
    }
    console.log('item:', item)
  }
}()

// repro-inferred.ts
new class {
  private map: Record<string, TypeName[]> = { x: ['f_0|i_0'] }

  constructor() {
    let item             // <== inferred, no explicit annotation (this is the ONLY difference to 'repro.ts')
    if (this.map.x) {
      const [entry] = this.map.x
      item = entry
    }
    console.log('item:', item)
  }
}()

// TypeName.d.ts
type TypeName = `${Prefix}${Suffix}`;
type Prefix =
    "f_0|" |
    "f_1|" |
    "f_2|" |
    ...
    "f_198|" |
    "f_199|";
type Suffix =
    "i_0" |
    "i_1" |
    ...
    "i_198" |
    "i_199";

🙁 Actual behavior

Type-checking takes ~30s for TS 6.0.3 and ~10s for TS 7.0.2 on a single file with
a 40k-union template literal type.

The runtime scales relative to the template dimension n (members = n²):

repro.ts

n	members	TS 6.0.3 (ms)	TS 7.0.2 (ms)
50	2500	971	458
100	10000	2468	826
150	22500	9433	3040
200	40000	27515	8852

Skipping the item assignment as seen in the repro-inferred.ts runs much
faster and wont scale exponentially.

repro-inferred.ts

n	members	TS 6.0.3 Inferred (ms)	TS 7.0.2 Inferred (ms)
50	2,500	798	415
100	10,000	816	405
150	22,500	892	407
200	40,000	842	407

🙂 Expected behavior

The type assignment should not slow things down and should run as fast as the
inferred file (repro-inferred.ts).

Additional information about the issue

Related issue: #63342

• similar union type-checking complexity (but the attached PR did not
  help with this bug - Use trie for removeStringLiteralsMatchedByTemplateLiterals #63343).

[RyanCavanaugh]

This might not be a bug; // repro-inferred.ts really does have to do less work than // repro.ts - the latter has to do an assignability check, the former does not.