Quadratic check time for diamond-shaped interface inheritance graphs

Chưa có ai nhận issue này.

## 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.

Bắt đầu với phần triển khai hasBaseType và so sánh bản sửa lỗi được đề xuất trong branch với bài kiểm thử hồi quy của compiler có tên interfaceExtendsDiamondPerformance. Chạy các lệnh xác thực được liệt kê ở đây, đặc biệt là bài kiểm thử đó và các bài kiểm thử kiểu cơ sở vòng. Hoàn tất khi repro diamond hoàn thành nhanh chóng mà không gây hồi quy cho các bộ kiểm thử compiler hiện có; một bản sửa lỗi được đề xuất và một branch đã tồn tại.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.