Quadratic check time for diamond-shaped interface inheritance graphs

还没有人认领这个 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.

从 hasBaseType 的实现开始，并将提议的 branch 修复与名为 interfaceExtendsDiamondPerformance 的编译器回归测试进行比较。运行此处列出的验证命令，尤其是该测试和循环基类型测试。完成的标准是 diamond 复现能够快速完成，同时不会导致现有编译器测试套件出现回归；提议的修复和 branch 已经存在。

由索引模型根据 Issue 内容生成。