Check order dependence with mutually-recursive non-unary generics

[erikbrinkman]

Bug Report

Adding an implementation of an interface allows an invalid assignability check of the interface to pass

🔎 Search Terms

assignability, unnecessary implementation

🕗 Version & Regression Information

• This changed between versions 3.7.5 and 3.8.3

It's still present in all versions including nightly.

⏯ Playground Link

Playground link with relevant code

Thanks @MartinJohns for the link

💻 Code

interface Parent<A, B> {
  getChild(): Child<A, B>;

  iter(): Iterable<Parent<A, B>>;
}

interface Child<A, B>
  extends Parent<A, B> {
  readonly a: A;
  readonly b: B;
}

class Impl<A, B> implements Parent<A, B> {
  constructor(readonly child: Child<A, B>) {
  }

  getChild(): Child<A, B> {
    return this.child;
  }

  *iter(): Iterable<Parent<A, B>> {
    const map = new Map<Child<unknown, unknown>, Child<A, B>[]>();

    function* gen(
      inp: Child<A, B>
    ): Iterable<Child<A, B>> {
      yield* map.get(inp) || [];
    }
  }
}

const x: Parent<unknown, unknown> = {} as any;
const _: Parent<null, unknown> = x; // should not pass

The final assignment should not pass. It accurately errors in 3.7.5, if the Impl class is removed (or any aspect of the iter implementation is modified), or by adding a sentinel type like sentinel?: A to the Parent interface to aid in type checking.

🙁 Actual behavior

No error is thrown in the final assignment.

🙂 Expected behavior

A n error is throw:

Type 'Parent<unknown, unknown>' is not assignable to type 'Parent<null, unknown>'.
  Type 'unknown' is not assignable to type 'null'.

[MartinJohns]

Unfortunately, this only occurs across several files, so I can't link to the playground.

It's reproducible on the playground: Playground link

Deleting the unused Impl class results in the error being shown.

[RyanCavanaugh]

Simplified and cleaned up a little to make the violation more apparent

interface Parent<A> {
  child: Child<A> | null;
  parent: Parent<A> | null;
}

interface Child<A, B = unknown> extends Parent<A> {
  readonly a: A;
  // This field isn't necessary to the repro, but the
  // type parameter is, so including it
  readonly b: B;
}

function fn<A>(inp: Child<A>) {
  // This assignability check defeats the later one
  const a: Child<unknown> = inp;
}

// Allowed initialization of pu
const pu: Parent<unknown> = { child: { a: 0, b: 0, child: null, parent: null }, parent: null };
// Should error
const notString: Parent<string> = pu;
// Unsound read on .child.a
const m: string = notString.child!.a;

[andrewbranch]

Debugging notes: variance measurement for Parent is getting set to VarianceFlags.Independent, implying that its type parameter is never witnessed at all. It arrived at this conclusion by checking the assignability of Parent instantiated with marker types. It first checks assignability in both directions with instantiations with super/sub-related marker types, and
assignability appears to return true in both directions; however, it actually is returning Ternary.Unknown, due to being unable to answer questions about the assignability of the types' parent and child properties without knowing their variances. After (incorrectly) concluding that Parent is bivariant on A, it checks another set of instantiations with markers that are unrelated to each other. That too comes back as Ternary.Unknown but is interpreted as true, so the variance gets updated to Independent, since instantiating Parent with all kinds of different markers with different assignability to each other apparently had no effect on the instantiations' assignability to each other.

I'm not sure if any of those comparisons ever actually looked at a and b, which should provide some non-recursive concrete variance information. I'm also not sure if outofbandVarianceMarkerHandler should have been called at some point, but it was not.

[andrewbranch]

@weswigham, I may need some help/advice on this one.

[weswigham]

We should probably make a Ternary.Unknown result witnessed by getVarianceWorker result in a Unmeasurable variance.

[andrewbranch]

The Ternary result isn’t returned from any top level function; it gets thrown out by checkTypeRelatedTo in order to return a boolean instead. I’m surprised we haven’t needed to distinguish between Ternary.Unknown and Ternary.True outside of that function before now—am I missing something?

[weswigham]

IIRC, when Unknown was added it was supposed to be a non-caching True - so existing truthy checks were sufficient in most places.

[Andarist]

I've spent the last 1.5 days debugging something that looks awfully like this one. This is way beyond my head and the understanding of the type system so I can't fully assess if my issue is exactly the same or just similar. Therefore I'm going to post it, for the time being, to avoid creating a new issue that might be a duplicate of this one.

TS playground

code from the playground

declare class StateNode<TContext, TEvent extends { type: string }> {
  // if I comment out this property then error is never reported
  _storedEvent: TEvent
  // if I comment out this property then error is always reported
  _action: ActionObject<TEvent>
  // if I comment out this property then error is always reported
  _state: StateNode<TContext, any>;
}

interface ActionObject<TEvent extends { type: string }> {
  exec: (meta: StateNode<any, TEvent>) => void
}

export declare function createMachine<
  TEvent extends { type: string }
>(action: ActionObject<TEvent>): StateNode<any, any>

export declare const execute: <TEvent extends { type: string }>(
  handler: (event: TEvent) => any
) => ActionObject<TEvent>;

export declare function interpret<TContext>(
  machine: StateNode<TContext, any>
): void

// uncomment to get a correct report in the `createMachine` call below
// const test: ActionObject<{ type: "PLAY"; value: number } | { type: "RESET" }> =
//   {} as ActionObject<{
//     type: "PLAY";
//     value: number;
//   }>;

const machine = createMachine({} as any);

// comment out to get a correct report in the `createMachine` call below
interpret(machine);

createMachine<{ type: "PLAY"; value: number } | { type: "RESET" }>(
  execute((ev: { type: "PLAY"; value: number }) => {
    console.log(ev);
  })
);

I've also found out that this has changed between 3.7 and 3.8. More accurately - between 3.8.0-dev.20200117 and 3.8.0-dev.20200118. If only I've tracked down correctly from which commits those two were built then the behavior change is related to this diff:
https://github.com/microsoft/TypeScript/compare/e2e1f6fd85b5076186ba6ee68fe59e11ccac1d3f..afa11d3c7ac37c49fc97230a897e4208ee132ae4
Given this diff, the change was introduced in this PR: #36261

I know that at this point I'm probably just reiterating what you probably already know but since I've already done this detective work I'm posting this here as a reference, just in case.

I also have a hunch that another issue that I've posted some months ago might be related to this one: #45859 (I would have to confirm this when this one here gets fixed)

[ahejlsberg]

Marking this as a design limitation. See rationale here. Note in particular that with #48240 it becomes possible to add variance annotations to establish the correct variance in the examples listed in this issue.