Structural Comparison of Circular Tuples

[harrysolovay]

TypeScript Version: 3.8.2

Search Terms: structure, resolve, compare, equality, type, mismatch, circular, tuple, cycle, recursive

Code

I'm trying to represent some type information for runtime use. I define the following enum:

enum Type {
  Int = "Int",
  List = "List",
}

And I define a Codec type: a tuple, within which the first element is the given Type enum value, and the second element––which is optional––is another Codec:

type Codec<
  T extends Type,
  C extends Codec<Type> | undefined = undefined
> = C extends undefined ? [T] : [T, C];

I'm able to assign Codecs as expected:

const c1: Codec<Type.Int> = [Type.Int];
const c2: Codec<Type.List, Codec<Type.Int>> = [Type.List, [Type.Int]];

And I'm able to create helpers for the Type.Int Codec:

type IntCodec = Codec<Type.Int>;
const createIntCodec = (): IntCodec => [Type.Int];
const intCodec = createIntCodec(); // signature is `[Type.Int]`

However, I'm unable to create helpers for Codecs which nest other Codecs:

type ListCodec<C extends Codec<Type>> = Codec<Type.List, C>;
const createListCodec = <C extends Codec<Type>>(of: C): ListCodec<C> => [Type.List, of]; // error

This results in an error: Type '[Type.List, C]' is not assignable to type 'Codec<Type.List, C>'. ts(2322).

Playground Link

Any thoughts would be greatly appreciated! Thank you!

[weswigham]

This is probably fixed by #35741.

[harrysolovay]

@weswigham awesome to hear! One more thing that I'd like to point out about this scenario:

const sadCodec: Codec<
  Type.List,
  Codec<
    Type.List,
    Codec<Type.Int>
  >
> = [Type.List, [Type.List, [Type.Int]]];

The above produces an error:

Type '[Type.List, [Type.Int]]' does not satisfy the constraint '[Type]'.
  Types of property 'length' are incompatible.
    Type '2' is not assignable to type '1'.

... even though the Codec type has an arity of 1 or 2. Hoping this helps with the solution. & thank you for adding to the 4.0 milestone!

[RyanCavanaugh]

I want to spin this into a new pair of issues. The problem can be more easily seen as a failure to propagate constraints

type Thing<A> = A extends string ? 1 : 2;
function fn1<T extends string>(n: T): Thing<T> {
  // Should be OK
  return 1;
}

function fn2<T extends string>(n: T): Thing<T & string> {
  // Is OK... but this is a no-op?            ^^^^^^^^
  return 1;
}

The example as written...

type Codec<
  T extends Type,
  C extends Codec<Type> | undefined = undefined
> = C extends undefined ? [T] : [T, C];

... is harder for us to analyze because its correct behavior depends on knowing that anything that could legally extend Codec<Type> could not possibly extend undefined, but that sort of counterfactual analysis is difficult to get right 100% of the time apart from these sorts of edge cases that can be easily rewritten anyway.

I had a local branch to copy the constraint to the restrictive instantiation but it caused new type constraint circularity errors in projects that were too complex to analyze in a reasonable amount of time.