Performance issue checking IndexedAccess rest parameter that resolves to large union of tuples

[brendankenny]

TypeScript Version: 3.1.0-dev.20180829, master

Search Terms: rest, parameters, union, tuple, IndexedAccess,

I realize this may be firmly in the camp of "doctor, it hurts when I do this", but thought I'd still file :)

I ran into this when using a union of tuples in place of overloading, not realizing it wasn't really supposed to be working until #26676. Since the tuples came from the values of an interface, I believe the indirect indexed access was allowing it to still pass since it would fall back to structural checking against any[].

With #26676 landed it's still an issue, though.

Code
This was from an attempt to type the Chrome debugger rpc protocol using tuples to represent that some commands need no parameters, some need one, and some can optionally have one. I'll link to the type files since they're large, but I can provide them elsewhere if needed: ChromeDevTools/devtools-protocol/pull/113/protocol-mapping.d.ts, and the types referenced in that file are found in protocol.d.ts. All the types end up relatively shallow and without cycles.

Poor performance can be triggered with

import ProtocolMapping  from './protocol-mapping';
type Commands = ProtocolMapping.Commands;

function sendCommand<C extends keyof Commands>(method: C, ...params: Commands[C]['paramsType']) {}

This takes ~6 seconds to check with tsc --strict on my machine, with about 3.5 seconds attributable to checkParameter() of ...params. More crucially it adds a similar amount of time to tsserver responses, and the work doesn't seem to be cached, so it re-runs on every intellisense completion.

On the other hand, the not quite equivalent

function sendCommand<C extends keyof Commands>(method: C, ...params: Commands[keyof Commands]['paramsType']) {}

takes about 2 seconds (with about 300 ms of that attributable to checkParameter of ...params).

The difference appears to come down to when the checker realizes the type is a union of tuples. The fast version does appear to end up checking each tuple for structural similarity to any[], but it does so for each tuple in the union individually, which is relatively fast.

The slow version seems to instead get deep enough that it ends up taking the union of each property across the tuples, then compares each of those against the properties of any[]. Since in this example basically each tuple ends up with a unique typeArgument, I assume the structural comparison against these unions for each property is what's taking the bulk of this time. The profile is mostly stuck in getPropertiesOfUnionOrIntersectionType down to createUnionOrIntersectionProperty and then splitting up into many nested isRelatedTo calls.

Hopefully the slow case could be made to function more like the fast case, but it also seems like a shortcut is possible since the tuples are never used for anything but rest parameters (so memoized type info is never used again) and as soon as getApparentType() is called with Commands[C]['paramsType'], the type then becomes a union of objects with ObjectFlags.Tuple, which could be used for an even quicker test.

To check, I added a super hacky isUnionOfTuples method and the time spent dropped to essentially nothing. I might be missing the corner cases here (or that my case is a special case of some tricky general issue), but if rest parameters for overloading becomes popular, it seems like a fast path for when the apparent type of source is a union of tuples and target === anyArrayType could be generally useful without much cost.

[RyanCavanaugh]

It's disappointing to see such a well-documented interface cause such problems on our side when simply having a declaration exist. I think it's worth looking in to what can be done. Naively, we might actually be able to completely defer the cost until an actual function call of sendCommand (at which point we could hopefully fix C much earlier); there's not an obvious reason to enforce the type of params at the declaration site.

To check, I added a super hacky isUnionOfTuples method and the time spent went to essentially nothing.

Would you mind throwing that up in a PR so we can evaluate it as a possible approach?

[brendankenny]

Before #26676 there was an explicit isRestParameterType so I had it called from there. checkParameter() seems more general, so not sure if that's the best place now.

function isUnionOfTuples(type: Type) {
    const apparentType = getApparentType(type);

    if (!(apparentType.flags & TypeFlags.Union)) {
        return false;
    }

    for (const constituentType of (<UnionType>apparentType).types) {
        if (!isTupleType(constituentType)) {
            return false;
        }
    }
    return true;
}

I don't really know if getApparentType() is the right thing to call (just that the object looked right when it came out) or if isTupleType() only passes for true tuples, but it worked for my code :)

edit: simplified the code, and verified on master that taking the cargo-culted isUnionOfTuples and adding it to the final rest-params check in checkParameter() still seems to work and the tests all pass

[ahejlsberg]

Looks like a bit of optimizing might be needed. I'll see what we can do.

[ahejlsberg]

With #26790 we're now down to 0.08 seconds for checking the example above (with --skipLibCheck to exclude checking of .d.ts files).

[brendankenny]

just checked too, it works great. Thanks!