Circularities Only Blocked Sometimes

[harrysolovay]

TypeScript Version: 3.8.2

Search Terms: circular, type, mapping, tuple, corresponding, signature

This builds off of the issue I just submitted (tagged as a bug).

In summary, I'm trying to create a virtual type system.

I define the available types:

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

I create a Codec type:

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

And I create a utility type, which can be used to unwrap / gather the corresponding type.

type AnyCodec = Codec<Type, Codec<Type> | undefined>;

type Decode<C extends AnyCodec> = C extends Codec<Type.Boolean>
  ? boolean
  : C extends Codec<Type.Int>
  ? number
  : C extends Codec<Type.List, Codec<Type>>
  ? C extends Codec<Type.List, infer I>
    ? I extends Codec<Type>
      ? Decode<I>[]
      : never
    : never
  : never;

Surely enough, it works for Codec<Type.Int>:

const intCodec: Codec<Type.Int> = [Type.Int];
type IntCodec = typeof intCodec;
type IntCodecDecoded = Decode<IntCodec>; // `string`

It works for Codec<Type.Boolean>:

const booleanCodec: Codec<Type.Boolean> = [Type.Boolean];
type BooleanCodec = typeof booleanCodec;
type BooleanCodecDecoded = Decode<BooleanCodec>; // `boolean`

And it works for Codec<Type.List>:

const listOfIntCodec: Codec<Type.List, Codec<Type.Int>> = [
  Type.List,
  [Type.Int],
];
type ListOfIntCodec = typeof listOfIntCodec;
type ListOfIntCodecDecoded = Decode<ListOfIntCodec>; // `number`

TypeScript Playground of the example up to this point

We see Decode works, even though it's self-referencing. There's no cycle-related error––presumably because of the use of tuples, which seem somewhat cycle-friendly since 3.7. Now let's add another type:

enum Type {
  Boolean = "Boolean",
  Int = "Int",
  List = "List",
+ Union = "Union",
}

We modify the Codec type to support multiple array of type Codec (the types to unite):

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

And we update the definition of AnyCodec:

type AnyCodec = Codec<Type, Codec<Type> | Codec<Type>[] | undefined>;

Let's instantiate this type:

const unionOfIntAndBoolean: Codec<
  Type.Union,
  [Codec<Type.Boolean>, Codec<Type.Int>]
> = [Type.Union, [[Type.Boolean], [Type.Int]]];
type UnionOfIntAndBoolean = typeof unionOfIntAndBoolean;

And let's create and use the corresponding DecodeUnion utility:

type DecodeUnion<C extends Codec<Type.Union, [Type][]>> = C extends Codec<
  Type.Union,
  infer T
>
  ? T extends AnyCodec[]
    ? T[number] extends AnyCodec
      ? Decode<T[number]>
      : never
    : never
  : never;

type UnionOfIntAndBooleanDecoded = DecodeUnion<UnionOfIntAndBoolean>; // `number` | `boolean`

TypeScript Playground of this example, continued up to this point

The utility works! UnionOfIntAndBooleanDecoded is inferred as being of type number | boolean. Last but not least, let's integrate DecodeUnion into the more general Decode utility type.

This is where we run into trouble:

type Decode<C extends AnyCodec> = C extends Codec<Type.Boolean>
  ? boolean
  : C extends Codec<Type.Int>
  ? number
+ : C extends Codec<Type.Union, [Type][]>
+ ? DecodeUnion<C>
  : C extends Codec<Type.List, Codec<Type>>
  ? C extends Codec<Type.List, infer I>
    ? I extends Codec<Type>
      ? Decode<I>[]
      : never
    : never
  : never;

TypeScript Playground, with the error-producing code

While the prior self-reference did not result in a circularity error, this one does: Type alias 'Decode' circularly references itself.

Is there a workaround? Could this be related to the aforementioned issue?

I know I've said it many times, but I truly mean it every time when I say: your help is greatly appreciated & thank you!!!

[soul-codes]

Sorry if I hijack this issue, but I truly am not sure whether what I'm also experiencing somehow has a similar root cause to the OP (similar issue search took me here). @harrysolovay perhaps you could see if the behavior described below contributes to/is related to your issue in any way?

The issue that I've come across is that if a generic interface (GenericBox) is directly part of a type alias (Foo), that type alias can use itself as generic argument to the generic interface. However, if the generic interface is then used as a part of a generic type alias (Bar), another type alias (UnionOfBar) sending itself as generic argument into this generic type will result in a circular reference error. (live)

interface GenericBox<T> {
  value: T;
}

type Foo = GenericBox<Foo> | string; // OK

type Bar<T> = GenericBox<T>;
type UnionOfBar = Bar<UnionOfBar> | string; // Circular reference error

[harrysolovay]

@soul-codes circularities are allowed in tuples, of which UnionOfBar is not. In tuples, it's possible to resolve the signature of the tuple to type-check its child elements, which might share their parent's signature. In the situation you describe, UnionOfBar's signature is unclear––it describes itself. Might I ask what is your use case? There's likely a better way to describe your data.

Also––if you wish to ask––please do so on StackOverflow, and link to your question from here. This forum is really only for bugs/potential bugs/feature requests.

[RyanCavanaugh]

This might be fixed by #37423 ; it's worth checking.

If not, this is kind of like how the police only sometimes pull you over for speeding. "Fixing" this probably won't be in the direction you want 😉

If you can narrow this down to a super simple example we could advise further

[soul-codes]

@harrysolovay understood. I just wondered if our issues were in fact the same and perhaps, as Ryan has requested, yours could simplify to mine. It seems like it is rather a misunderstanding of how circularity is supposed to work on my side which led me to mistake it as a bug/issue. I will proceed to SO accordingly. Sorry to pollute this issue folks!

[harrysolovay]

I was definitely speeding 😂

I managed to implement the desired type-mapping thanks to a StackOverflow answer provided by the creator of Punchcard, a serverless DX, which I encourage all to check out!

One of the monorepo's packages, "Shapes" (like "Codecs"), is used to map between the representations of different services while enforcing type-safety. Really, really cool. Anyone who's trying to achieve recursive mapping between types should check it out.