Quadratic check time for diamond-shaped interface inheritance graphs

[canonic-epicure]

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:

7964e22f2b85f16e520f0e902c7fd7b6f0c15416

Code

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

Full repro

// @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:

Check time: 0.01s
Total time: 0.13s

Proposed fix

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

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

    const seen = new Set<Type>();

    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:

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

Commit:

51938c85a396151a93ac0101f94c66a55dfafa14

Additional information

The branch contains:

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

Validation run:

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

Result:

89845 passing

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

[MartinJohns]

@m-mahdi-abbaszade You should read this and stop with your pointless spam: https://github.com/microsoft/TypeScript/blob/main/CONTRIBUTING.md#automated-comments

[RyanCavanaugh]

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

This doesn't meet the 6.0 patch bar. We could evaluate a PR in the Go repo; that said, it seems like this would make the by-far modal case (slightly) slower for the sake of a thing you probably shouldn't be doing in the first place.

[canonic-epicure]

Its a valid program after all => should compile.

[RyanCavanaugh]

A Turing-complete system that can produce correct outputs in finite and bounded time is going to be extremely useful 😉

[canonic-epicure]

I agree, definitely, its very important to apply a proper fix.