Undetected illegal assignment of nested array types

[martinwepner]

Bug Report

Typescript does not allow the assignment of Source4 to Target4 which is expected because they are incompatible. After 3 or more levels of nested array properties this error is not detected anymore. Even the errors on the nested types may disappear depending on the order of the assignments.

Note: every type is explicitly named and there are no cycles.

(This actually caused problems in our production codebase)

🔎 Search Terms

nested array assignment, undetected illegal assignment of nested array types, undetected illegal assignment, illegal assignment

🕗 Version & Regression Information

• In versions before 4.5.3: limit of nested array levels is 5 instead of 3
• This changed between versions 4.4.4 and 4.5.3 (to 3 levels)
• PRs:
  • bisect: 🤖 Pick PR #46599 (Improve recursion depth checks) into release-4.5 #46974 (thank you @pyBlob for bisect)
  • main: Improve recursion depth checks #46599
    • maybe: isDeeplyNestedType maxDepth check?

⏯ Playground Link

Playground link with relevant code

💻 Code

type Source1 = { array: Source2[] };
type Source2 = { array: Source3[] };
type Source3 = { array: Source4[] };
type Source4 = {};

// same as Source types but with "someNewProperty"
type Target1 = {
  array: Target2[];
  // someNewProperty: string // error in target1 assignment as expected if enabled
};
type Target2 = {
  array: Target3[];
  // someNewProperty: string // error in target1 assignment as expected if enabled
};
type Target3 = {
  array: Target4[];
  // someNewProperty: string // error in target1 assignment as expected if enabled
};
type Target4 = {
  someNewProperty: string; // not existing in Source4 => no error in target1 assignment
};

declare const source1: Source1;
declare const source2: Source2;
declare const source3: Source3;
declare const source4: Source4;

// this should not compile:
const target1: Target1 = source1; // comment this line to get errors in target2, target3 assignments or move this line after target2 assignment

// this should not compile:
const target2: Target2 = source2; // error if target1 assignment is commented or after this assignment

// this should not compile:
const target3: Target3 = source3; // error if target1 assignment is commented or after target2 assignment

// does not compile:
const target4: Target4 = source4; // error as expected

/*
PS:
- same (wrong) behavior with interfaces and classes
*/

🙁 Actual behavior

• Source1 is assignable to Target1
• Source2 is assignable to Target2
• Source3 is assignable to Target3
• Reordering of assignments impact type checking
  • If source1 assignment is skipped or moved after source2 assignment the expected errors show

🙂 Expected behavior

• Source1 is not assignable to Target1

Type 'Source1' is not assignable to type 'Target1'.
  Types of property 'array' are incompatible.
    Type 'Source2[]' is not assignable to type 'Target2[]'.
      Type 'Source2' is not assignable to type 'Target2'.
        Types of property 'array' are incompatible.
          Type 'Source3[]' is not assignable to type 'Target3[]'.
            Type 'Source3' is not assignable to type 'Target3'.
              Types of property 'array' are incompatible.
                Type 'Source4[]' is not assignable to type 'Target4[]'.
                  Property 'someNewProperty' is missing in type 'Source4' but required in type 'Target4'.

• Since Source1 is a fixed/static tree (without any self references) I expect the error to be found by the compiler.
• Reordering of assignments do not impact type checking results

Related issues

#42070

[RyanCavanaugh]

The root cause here is that we need to bail out at some point during nested evaluation of a type, since we have no way to know that we're not encountering an infinitely generatively-nested recursive type, e.g.:

type Nested<T> = {
  a: T;
  b?: Nested<Nested<T>>;
}

"Ah, but this type is just an ever-deeper instantiation of the same thing over and over again, which would be trivial to detect, whereas OP is totally different" you say. But the stack here looks just like the stack in the original report, because we keep visiting ever-deeper instantiations of the same type -- Array<T>. The same behavior can be seen with a non-array generic type:

type Box<T> = { value: T };

type Source1 = { array: Box<Source2> };
type Source2 = { array: Box<Source3> };
type Source3 = { array: Box<Source4> };
type Source4 = {};

// same as Source types but with "someNewProperty"
type Target1 = {
  array: Box<Target2>;
  // someNewProperty: string // error in target1 assignment as expected if enabled
};
type Target2 = {
  array: Box<Target3>;
  // someNewProperty: string // error in target1 assignment as expected if enabled
};
type Target3 = {
  array: Box<Target4>;
  // someNewProperty: string // error in target1 assignment as expected if enabled
};
type Target4 = {
  someNewProperty: string; // not existing in Source4 => no error in target1 assignment
};

declare const source1: Source1;
declare const source2: Source2;
declare const source3: Source3;
declare const source4: Source4;

// this should not compile:
const target1: Target1 = source1; // comment this line to get errors in target2, target3 assignments or move this line after target2 assignment

// this should not compile:
const target2: Target2 = source2; // error if target1 assignment is commented or after this assignment

So if anyone wants to try to fix this they're welcome to come up with some new detection mechanism, but any fix here needs to a) not tank performance in normal scenarios and b) not introduce new circularity or complexity errors in real code either.

Note that it's also not sufficient to detect Nested via the instantiations being "adjacent" in the call stack - Nested might ping-pong with another type (or even a series of other types, via conditional types) as it marches toward infinity.

[martinwepner]

Hi @RyanCavanaugh,

thank you for your quick response! I think "Cursed?" is the right label for this. What actually surprised me was that this problem has not been reported yet.

When using Typescript-based ORMs like @prisma, you can run into this kind of problem very quickly when joining some tables. In our case, the following data structure triggered the error (simplified):
Order->Payment[]->Refund[]->RefundOrderItemAmount[]`.

I am not familiar with the TS codebase, but given your example of the infinitely recursive Nested type, I would indeed have asked why it is so hard to detect. When building a "type tree" (I don't know the correct term) for Source1, there are no cycles or self-references (so there is no path through the tree back to the Source1 type) compared to the Nested type, which quickly references back to itself (Nested.b->Nested ==> cycle detected; no tree => treat differently than a tree).

type Ping = { pong: Pong };
type Pong = { ping: Ping };

Naively, isn't it trivial to discover the circle here too?
Type to parse Ping: Ping.pong=>Pong.ping=>Ping ‼️ cycle detected.
If you parse conditional types isn't it possible to parse all possible ways to also be able to detect a tree vs a graph?
But as I said I know nothing about the typescript codebase and probably one can easily find a more complex example that is not that trivial to detect.

But anyway, I find both your Source-Box and my Source-Array example scary. Typescript promises to be "A Result You Can Trust" and this is a very simple and not so far-fetched example where typescript breaks that promise.

If you could give me some starting points within the codebase to investigate this problem, I would be happy to help find a solution.

[RyanCavanaugh]

Naively, isn't it trivial to discover the circle here too?
Type to parse Ping: Ping.pong=>Pong.ping=>Ping ‼️ cycle detected.

That's not what's happening in the provided example. You're talking about detecting cycles, but we're not talking about cycles here, but rather infinite descent of novel types the whole way down. In other words, although there are referential cycles, there are not cycles of the same types - we're talking about increasingly-deep instantiations of the same types.

If you could give me some starting points within the codebase to investigate this problem, I would be happy to help find a solution.

You can add this line: main...RyanCavanaugh:TypeScript:stackDemo#diff-d9ab6589e714c71e657f601cf30ff51dfc607fc98419bf72e04f6b0fa92cc4b8R22654 to remove the depth limit. Then start trying to figure out how to make all the newly-failing tests in the same commit pass again, e.g. this one: main...RyanCavanaugh:TypeScript:stackDemo#diff-b92eac93adfa5c33adb53f3e9689088003bc273d7ec04382d0573f6944055897R25

This testcase, shown here failing if the depth limit didn't exist, is a good demonstration. In order to see if B<T> is a legal A<T>, you have to be able to answer the question of whether A<B<A<B<A<B<A<B<A<B<T .... is related to B<A<B<A<B<A<B<A<B<A<T ..., at infinite depth. But you can't go infinitely deep, and you can't just say "no" ("no" is the wrong answer here), so you have to have some strategy that terminates in finite time but still produces the most-possibly-correct answers.

Fair warning: if we had any idea how to fix this, it wouldn't be Cursed (and would have been fixed already). PRs surely welcomed but this isn't a case of us simply not having tried to fix it before.