ConditionalRoot.isDistributive is buggy

[markw65]

Bug Report

ConditionalRoot.isDistributive is a flag that indicates that a conditional "distributes" over union. Its set to true when the checkType is a TypeParameter. When its true, two main things happen:

• getIndexOfMappedType converts keyof { [ K in Keys as DistributiveConditional<K> ] : X } to DistributiveConditional<Keys> which is clearly unsound in many cases (this is the bug reported in Incorrect optimization for keyof Mapped type #43920).
• instantiateConditionalType attempts to undo what it assumes getIndexOfMappedType did. This sometimes prevents bugs that getIndexOfMappedType would otherwise have introduced, but for other cases can break the conditional.

For the first case, here's a simplified version of the example from #43920

type KeysExtendedBy<T,U> = keyof {[K in keyof T as U extends T[K] ? K :never] : T[K]};
interface M {
  a: boolean;
  b: number;
}
function f(x : KeysExtendedBy<M,number>) {
  return x;
}
f("a"); // <- f should only accept "b" as a parameter.

Here, getIndexOfMappedType optimizes KeysExtendedBy<T,U> to U extends T[keyof T] ? keyof T : never (which is clearly wrong). And in this case, instantiateConditionalType can't fix it, because it only tries to spread on the checkType.

This can be fixed by adding a redundant guard:

type KeysExtendedBy<T,U> = keyof {[K in keyof T as T[K] extends unknown ? U extends T[K] ? K : never : never] : T[K]};

Now the top level conditional is not isDistributive, and we don't call getIndexOfMappedType.

For the second case:

type Bug<T, U> = U extends "a" ? T[U & keyof T] : never;
interface M {
  a: boolean;
  b: number;
}
function f(x : Bug<M, "a"|"b">) {
  return x;
}
f(false);

Clearly, "a"|"b" does not extend "a", so f's parameter type should be never. But instantiateConditionalType notes that root.isDistributive is set (since U is a TypeParameter), and that checkType is a union (the keys of M), and so it replaces the conditional with ("a" extends "a" ? M["a"] : never) | ("b" extends "a" ? M["b"] : never) which reduces to M["a"] which is boolean.

I think these bugs show pretty conclusively that setting isDistributive whenever the checkType is a TypeParameter is broken. Perhaps only doing it when the checkType is a MappedType's type parameter (ie the K above) would be safe; but even then I think it often relies on instantiateConditionalType to fix it. Consider eg:

type KeysExtendingLiteral<T> = keyof {
  [K in keyof T as K extends "b" ? K : never] : T[K];
}
interface M {
  a: boolean;
  b: number;
}
function f(x: KeysExtendingLiteral<M>) {
  return x;
}
f("b");

KeysExtendingLiteral gets converted to keyof T extends "b" ? "b" & keyof T : never (you can see this by hovering over KeysExtendingLiteral in line 8 of playground example 3) - which again, is not the same thing. The original should evaluate to "b" whenever T has a "b" field, and never otherwise. The modified version evaluates to never unless T has a "b" field, and no other fields. However, in this case, we do get the correct results - because instantiateConditionalType converts it back to a union of individual tests - ie ("a" extends "b" ? "b" & "a" : never)|("b" extends "b" ? "b" & "b" : never)

My proposal is to rip out the isDistributive code altogether. The delicate dance where we first transform to an incorrect conditional, hope nobody notices, and then transform it back again at the end seems horribly unsound.

If this is really important for type inference, maybe the solution is to only call getIndexOfMappedType when the checkType is the MappedType's type parameter, and then set another flag to indicate the transformation was done, and have instantiateConditionalType check that flag. I'm not 100% convinced that's sound, but it should be much better than the current situation.

🔎 Search Terms

isDistributive

I found #43920 (my own report) which turns out to be a special case of the problems with isDistributive, and #30152 which appears to be a different problem.

🕗 Version & Regression Information

Its present on master, and has been since at least 4.1.5

• This is the behavior in every version I tried, and I reviewed the FAQ for entries about it.

⏯ Playground Links

Example 1
Example 2
Example 3

💻 Code

type KeysExtendedBy<T,U> = keyof {[K in keyof T as U extends T[K] ? K : never] : T[K]};
interface M {
  a: boolean;
  b: number;
}
function f(x : KeysExtendedBy<M,number>) {
  return x;
}
f("a");

🙁 Actual behavior

The call to f("a") is deemed correct

🙂 Expected behavior

It should fail because number does not extend M["a"] which is boolean, so "a" should not be included in the keys of the mapped type (and note that it isn't included in the mapped type itself).

[markw65]

@RyanCavanaugh You asked for clarification on #43920. My investigation led to a rabbit hole which ended up here. Maybe you could take a look at this?

[markw65]

Another interesting example, this time because keyof(A|B) === keyof(A) & keyof(B) and not keyof(A) | keyof(B).

[RyanCavanaugh]

@ahejlsberg thoughts?

[markw65]

It turns out you can't just kill isDistributive, because certain builtins rely on the broken behavior. eg

type Exclude<T, U> = T extends U ? never : T;

only works because instantiateConditionalType's distributes the union, changing the meaning of the type.

This definition works either way though [edit: but only for 'keyof' types]:

type Exclude<T extends string|number|symbol, U> = keyof { [K in T as K extends U ? never : K]: true};

[ahejlsberg]

Yeah, we're not quite doing the right thing here. A type keyof { [K in X as Y]: ... } can be simplified to an instantiation of Y with X substituted for K only when Y is distributive with respect to K. We're currently just checking that Y is distributive in general, but that isn't enough as demonstrated by the examples in this issue.

BTW, the notion of distributive conditional types isn't "broken" per se, it's simply a behavior we've chosen because the alternative (always non-distributive) would require an explicit for K in X: Y construct or some such for cases where distributive behavior is desired--which really turns out to be most of the time. The thing that's broken here is that we aren't doing the right thing for as T clauses in mapped types.

Also, I should mention that a quick workaround for the issue is to write a non-distributive type in the as clause:

type KeysExtendedBy<T, U> = keyof { [K in keyof T as [U] extends [T[K]] ? K : never] : T[K] };

But we should fix this so the workaround isn't required.

[markw65]

@ahejlsberg Thanks for the explanations. After investigating a few test failures due to killing off isDistributive, I was starting to think it must be intentional. But its still very surprising that the behavior of a conditional depends on whether the checkedType is a type-parameter or not.

eg modifying my second example a bit:

interface M { a: boolean; b: number; }
type U = "a"|"b";
type NoDist<T> = U extends "a" ? T[U & keyof T] : never;
type Dist<T, U = "a"|"b"> = U extends "a" ? T[U & keyof T] : never;

Its pretty surprising (to me) that NoDist<M> is never, but Dist<M> is boolean. Especially as this is the kind of change (starting with NoDist and ending with List) that happens as you generalize type definitions.

Finally wrt your workaround; that's fine now... but what happens when tsc v42.1 starts optimizing [foo] extends [bar] to foo extends bar. eg I already found that type NoDist<T, U> = (T|never) extends U ? never : T; doesn't actually work - it still gets distributed. By the time isDistributive is computed (T|never) has been simplified to T. On the other hand type NoDist<T, U, N = never> = (T|N) extends U ? never : T; does work (but of course, someone could pass something other than never as the third parameter).

[RyanCavanaugh]

but what happens when tsc v42.1 starts optimizing [foo] extends [bar] to foo extends bar

@markw65 We wouldn't. Any design looks bad if you start speculating about what would happen in the presence of bad decisions - the key is to not make bad decisions.

[markw65]

So what constitutes a bad decision in this context? Optimizing (T|never) to T was evidently not considered a bad decision, even though it dramatically changes the behavior of a conditional type if its the checkedType, and T is a TypeParameter.

Are you saying that the set of optimizations that typescript will perform is now fixed for all time?

[RyanCavanaugh]

Are you saying that the set of optimizations that typescript will perform is now fixed for all time?

I don't understand what this sort of strawmanning is trying to get at. Of course we need to restrict ourselves to optimizations that don't change the semantics of the operation, just like any other program ever written. We can't "optimize" [T] extends [U] to mean T extends U any more than we would "optimize" 2 * 3 to 2 + 3; per the rules of those operation they have different meanings and need to be treated differently. It's not, as a result, some design defect of multiplication and addition that they can't be arbitrarily substituted for each other - they are different.

[markw65]

@RyanCavanaugh Sorry, I'm genuinely puzzled here.

I assumed [T] extends [U] was equivalent to T extends U partly because plugging in some types, they seem to give the same answer, but mostly because @ahejlsberg told me I could replace T extends U with [T] extends [U] as a workaround for the problem.

I've been going through my code looking for conditional types that are distributive as written, but where I don't want the distributive behavior, and I've applied that suggestion to them (and as a result found a couple of bugs in my code). So my concern was, if the rewrite is identical in meaning to the original, what's to prevent a future optimization from undoing the rewrite, and breaking my code again? But if they're not the same, my new concern is when are they different, and does it affect any of the conditionals I've just rewritten?

But I was really trying to point out what appears to be a flaw in the implementation. Distributive Conditional Types talks about naked type parameters, but tsc seems to implement it as naked after applying optimizations (since (T|never) is considered naked). Perhaps [T] extends [U] being replaced by T extends U will never happen; but in general if I use some trick to make a conditional non-distributive, how do I know the trick will work in the future?

[RyanCavanaugh]

That's a good question. I think we're using the word "optimization" differently here. I was interpreting this to mean "performance enhancement", I think you mean something closer to what I call "resolution".

You've seen the code too and I think the clearest (though by no means clear) explanation is that if the test type, without regard to the right operand of extends, semantically resolves to "a type parameter", then the type is distributive. It's not a syntactic operation, so simplifications like T | never -> T or T & unknown -> T are possible to occur here.

There's no semantic resolution of [T] that will lead to the result of "this is a type parameter", because it's not. [T] is a tuple containing a type parameter, not a type parameter. There's no legal optimization that can occur to strip away [ ] here, because it would be semantics-affecting. In other words, it's not correct to do "do ___ to both sides of the equation"-style reasoning.

how do I know the trick will work in the future?

Because it's not a trick. The right side of the extends clause is not used at all when determining whether the left side is semantically a type parameter. As long as you're thinking about this semantically, you can make correct predictions:

type Id<T> = T;
// Still distributive, because Id<T> resolved to a type parameter T
type A<T> = Id<T> extends string ? "A" : "B";

declare class M<T> {
  // Still distributive; resolves to a type parameter
  f(): { a: T }["a"] extends string ? "A" : "B"
}

const s = new M<string | number>();
const a = s.f();

[markw65]

Thanks - that makes things a little clearer, although it makes the definition of a distributive conditional much harder to pin down.

Before I saw your last comment, I was experimenting with changing the isDistributive condition to:

  isDistributive: !!(checkType.flags & TypeFlags.TypeParameter && node.checkType.kind === SyntaxKind.TypeReference),

Which seems to be enough to only allow a syntactic type param, rather than anything that resolves to a type param (its possible this is the wrong check; I was surprised to find that I had to check for SyntaxKind.TypeReference, rather than SyntaxKind.TypeParameter). Now T|T, T|never and even (T) all prevent the conditional from being distributive - which appears to match the documentation for distributive conditionals much better than the current behavior. [edit: your Id<T>
example is still distributive; I guess Id is also a TypeReference, so we would also need a check that the names match].

The tests all pass with this... but from what you wrote above, you want it to treat anything that resolves to a type parameter as distributive. Is that really the case?

[RyanCavanaugh]

Generally people like to point to "consistency" as a boon, and here (as is often the case) we have competing definitions of what consistent would mean:

• Distributivity depends on the test type being both syntactically and semantically a type parameter reference (your proposal)
• In any program, you can substitute T with Id<T> without changing its meaning because those are the same thing in everything but spelling (the current behavior)

In general the type system depends on semantics, not syntax, so enforcing a new syntactic rule is potentially confusing even if it seems nominally simplifying in some other way. I think there should be a strong argument for why Id<T> needs to behave differently from T, since the default assumption really should be that they behave the same (the motivating scenario for type aliases is to be able to create names that have identical function to their referents).

Why would you want to change it? Hearing the motivation behind that would be instructive.

[markw65]

I guess my reasoning is that it would match what the documentation says. I mean, sure, you can argue that { a: T}["a"] really is a 'naked type parameter' but now you're requiring typescript users to know lots of details of the typescript implementation that they really shouldn't need to know.

I think it was a mistake to not have specific syntax for distributive conditionals (eg something like |U extends T to make it distributive) - but clearly its too late to fix that. Accepting that it can't be fixed, making the rule as clear as possible seems like the next best option.

[RyanCavanaugh]

I don't necessarily disagree with anything there, but will point out that it's really rather difficult to write a type expression that resolves to exactly a type parameter (except via a trivial why-even-do-that epicycle like the one you wrote), so in practice this is very rarely encountered.

[RyanCavanaugh]

Re the documentation, I think this is still broadly consistent. If you see us say in the docs, for example, "If foo is an array type, then Y, otherwise X", then you can interchangeably use string[], Array<string>, or MyArr (via type MyArr = string[];) with the same result. You don't need to understand how TypeScript is implemented to see the equivalence class there. If we say "naked type parameter", that has the same semantic interpretation.

In the few cases where we do make distinctions on syntax vs semantics (e.g. you cannot legally write { [s: MyStringAlias]: number }), the feedback has been overwhelmingly negative.

[markw65]

From my point of view, being a TypeParameter isn't part of the type system. At least, not in the way that being an array type or being a union type is a part of the type system. In fact being a TypeParameter especially a naked TypeParameter really seems to be part of the syntax... but as currently implemented by tsc its not (quite).

I guess I thought this was obviously the intent, but clearly reasonable people disagree - and absent a spec, it's hard to argue what the (rather vague) description in the documentation is supposed to mean. So I'll concede at this point. Thanks taking the time to explain all this.

[markw65]

@RyanCavanaugh Sorry, I had one more thought. Using the resolved type to determine whether or not a conditional is distributive means that some conditionals will be distributive with some compiler options, but not with others. eg type MaybeDistributive<T, U> = T|null extends U|null ? T : never; is distributive unless compiled with strictNullChecks (btw, I tried to set this up in the playground, but I found that although I can specify the tsconfig, I couldn't make the playground actually use it; no matter what I did, strictNullChecks was off - even though the checkbox is ticked by default).

This definitely seems wrong to me... I mean, obviously, strictNullChecks is supposed to change the behavior of the program, but this is a pretty unexpected change.

I also found, (rather surprisingly to me) that (T[])[number] is always considered to be a naked type parameter, regardless of strictNullChecks or noUncheckedIndexedAccess. That seems like a bug (independent of distributive conditionals). eg

function g(x : (T[])[number]) { return x; }
g(undefined);

Should accept the call to g, since x should be of type number|undefined (or am I missing something here)? There's a similar issue with Record<string,T>["foo"]. And of course, I was looking at this kind of expression because I expected it to be another expression whose nakedness depended on compile time options...