Quadratic check time for diamond-shaped interface inheritance graphs

Personne n'a encore pris cette issue.

## Search Terms

hasBaseType, interface inheritance performance, diamond-shaped interface inheritance, base type traversal, quadratic check time

## Version & Regression Information

This reproduces on TypeScript 6.0.3 and on current `main` before the proposed fix.

Tested current `main` commit:

```text
7964e22f2b85f16e520f0e902c7fd7b6f0c15416
```

## Code

The repro is an interface-only diamond-shaped inheritance graph. Each interface extends up to 8 previous interfaces.

Full repro

```ts
// @strict: true
// @noEmit: true

interface I0 {
p0_0: number;
}

interface I1 extends I0 {
p1_0: number;
}

interface I2 extends I1, I0 {
p2_0: number;
}

interface I3 extends I2, I1, I0 {
p3_0: number;
}

interface I4 extends I3, I2, I1, I0 {
p4_0: number;
}

interface I5 extends I4, I3, I2, I1, I0 {
p5_0: number;
}

interface I6 extends I5, I4, I3, I2, I1, I0 {
p6_0: number;
}

interface I7 extends I6, I5, I4, I3, I2, I1, I0 {
p7_0: number;
}

interface I8 extends I7, I6, I5, I4, I3, I2, I1, I0 {
p8_0: number;
}

interface I9 extends I8, I7, I6, I5, I4, I3, I2, I1 {
p9_0: number;
}

interface I10 extends I9, I8, I7, I6, I5, I4, I3, I2 {
p10_0: number;
}

interface I11 extends I10, I9, I8, I7, I6, I5, I4, I3 {
p11_0: number;
}

interface I12 extends I11, I10, I9, I8, I7, I6, I5, I4 {
p12_0: number;
}

interface I13 extends I12, I11, I10, I9, I8, I7, I6, I5 {
p13_0: number;
}

interface I14 extends I13, I12, I11, I10, I9, I8, I7, I6 {
p14_0: number;
}

interface I15 extends I14, I13, I12, I11, I10, I9, I8, I7 {
p15_0: number;
}

interface I16 extends I15, I14, I13, I12, I11, I10, I9, I8 {
p16_0: number;
}

interface I17 extends I16, I15, I14, I13, I12, I11, I10, I9 {
p17_0: number;
}

interface I18 extends I17, I16, I15, I14, I13, I12, I11, I10 {
p18_0: number;
}

interface I19 extends I18, I17, I16, I15, I14, I13, I12, I11 {
p19_0: number;
}

interface I20 extends I19, I18, I17, I16, I15, I14, I13, I12 {
p20_0: number;
}

interface I21 extends I20, I19, I18, I17, I16, I15, I14, I13 {
p21_0: number;
}

interface I22 extends I21, I20, I19, I18, I17, I16, I15, I14 {
p22_0: number;
}

interface I23 extends I22, I21, I20, I19, I18, I17, I16, I15 {
p23_0: number;
}

interface I24 extends I23, I22, I21, I20, I19, I18, I17, I16 {
p24_0: number;
}

interface I25 extends I24, I23, I22, I21, I20, I19, I18, I17 {
p25_0: number;
}

interface I26 extends I25, I24, I23, I22, I21, I20, I19, I18 {
p26_0: number;
}

interface I27 extends I26, I25, I24, I23, I22, I21, I20, I19 {
p27_0: number;
}

interface I28 extends I27, I26, I25, I24, I23, I22, I21, I20 {
p28_0: number;
}

interface I29 extends I28, I27, I26, I25, I24, I23, I22, I21 {
p29_0: number;
}

interface I30 extends I29, I28, I27, I26, I25, I24, I23, I22 {
p30_0: number;
}

interface I31 extends I30, I29, I28, I27, I26, I25, I24, I23 {
p31_0: number;
}

declare const value: I31;
value.p0_0;
```

## Actual behavior

Before the fix, compiling the repro above timed out after 30 seconds.

The hotspot is `hasBaseType`, which recursively walks `getBaseTypes(target)` and can revisit the same reachable base-type subgraphs many times during one query.

## Expected behavior

The checker should avoid revisiting the same base-type subgraph during a single `hasBaseType` query.

With a per-call `seen` set in `hasBaseType`, the same repro completes quickly:

```text
Check time: 0.01s
Total time: 0.13s
```

## Proposed fix

The fix is to keep a per-call `Set` inside `hasBaseType` and skip already visited class/interface/reference/intersection nodes.

```ts
function hasBaseType(type: Type, checkBase: Type | undefined) {
if (!checkBase) {
return false;
}

const seen = new Set();

return check(type);
function check(type: Type): boolean {
if (getObjectFlags(type) & (ObjectFlags.ClassOrInterface | ObjectFlags.Reference)) {
const target = getTargetType(type) as InterfaceType;
if (target === checkBase) {
return true;
}
if (seen.has(target)) {
return false;
}
seen.add(target);
return some(getBaseTypes(target), check);
}
else if (type.flags & TypeFlags.Intersection) {
if (seen.has(type)) {
return false;
}
seen.add(type);
return some((type as IntersectionType).types, check);
}
return false;
}
}
```

I have pushed a branch with the proposed fix and regression test here:

```text
https://github.com/canonic-epicure/TypeScript/tree/fix-has-base-type-seen
```

Commit:

```text
51938c85a396151a93ac0101f94c66a55dfafa14
```

## Additional information

The branch contains:

- the `hasBaseType` fix;
- the compiler regression test shown above;
- updated baselines.

Validation run:

```bash
npx hereby local
npx hereby runtests --tests=interfaceExtendsDiamondPerformance
npx hereby runtests --tests='interfaceThatIndirectlyInheritsFromItself|interfaceThatInheritsFromItself|circularBaseTypes|infinitelyExpandingBaseTypes1'
npx hereby runtests --runner=compiler
```

Result:

```text
89845 passing
```

I can open a PR with the fix if this is considered appropriate for the JS-based TypeScript repository maintenance policy.

Commencez par l’implémentation de hasBaseType et comparez le correctif proposé dans la branch avec le test de régression du compilateur nommé interfaceExtendsDiamondPerformance. Exécutez les commandes de validation listées ici, en particulier ce test et les tests de types de base circulaires. C’est terminé lorsque le repro en diamant s’achève rapidement sans provoquer de régression dans les suites de tests existantes du compilateur ; un correctif proposé et une branch existent déjà.

Rédigé par le modèle d'indexation à partir du texte de l'issue.