CODEWITHSUNDEEP
typescript
Rui Gonçalves
Rui Gonçalves

Reputation: 1375

Self-referencing a mapped type in TypeScript

I'm modeling an AST for a small language in Typescript. I'm trying to transform this type:

type Lang<T> = {
  Literal: { value: string | number | boolean },
  BinOp: { op: string, lhs: T, rhs: T },
  UnOp: { op: string, arg: T },
  // ...more fields
};

Into this:

type ASTNode =
  { type: 'Literal', value: string | number | boolean } |
  { type: 'BinOp', op: string, lhs: ASTNode, rhs: ASTNode } |
  { type: 'UnOp', op: string, arg: ASTNode }
  // ... more types
;

I think the solution is something along these lines:

type ASTNodeAux<T> = {
    [K in keyof Lang<T>]: { type: K } & Lang<T>[K]
};
type ASTNode = ASTNodeAux<ASTNode>[keyof ASTNodeAux<ASTNode>];

But this isn't accepted by TypeScript since ASTNode references itself. From what I saw the workaround is usually to use interfaces instead, but I don't see how I can do this together with mapped types. Is there any way to achieve this?

For extra context, I am trying to avoid the need to write type types multiple times while providing accurate type signatures for AST nodes and the arguments of fold, forEach and other combinators (playground link). I was able to achieve this (in a somewhat imperfect way) in Flow (playground link).

Upvotes: 2

Views: 496

Answers (1)

Hugo Sereno Ferreira
Hugo Sereno Ferreira

Reputation: 8631

UPDATE: After going through your playground, it becomes more clear why you want a Lang<T> specified in that way. Here's some code on the playground using a subset of your own example and where render, run and fold seem to type successfully, using the following definitions:

type Replace<T, B> = { [P in keyof T]: T[P] extends SSNode ? B : T[P] }
type ASTNodeMatch <K, T> = Omit<Extract<Replace<SSNode, T>, { type: K }>, 'type'>
type SSAction<T, U> = { [K in SSNode['type']]: (x: ASTNodeMatch<K, T>) => U }

Me and André Restivo have been working in the past 4 hours on this :) We provide two answers, depending on which direction you want to go. However, we think that your Lang<T> is ill-formed. What exactly is the T supposed to be? Maybe the terminal values? If that is the case, then the lhs and rhs should point to Lang<T> and the Literal should be of type T and not string | number | boolean. Another thing is that your Lang properties should all be optional (or else any instance of Lang would force it to provide a Literal, UnOp, BinOp, and so on...) We trust you will fix the code appropriately to match your language semantics...

P.S. There is a lot of "intermediate" types that you can get rid of, but we believe this makes it easy to follow the rationale.

Going from a Descriminated Union Type to a Lang:

namespace OneWay {
    /* type Lang<T> = {
    Literal?: { value: string | number | boolean },
    BinOp?: { op: string, lhs: T, rhs: T },
    UnOp?: { op: string, arg: T },
    } */

    type ASTNode =
        { type: 'Literal', value: string | number | boolean } |
        { type: 'BinOp', op: string, lhs: ASTNode, rhs: ASTNode } |
        { type: 'UnOp', op: string, arg: ASTNode }

    type Replace<T, A, B> = {
        [P in keyof T]: T[P] extends A ? B : T[P]
    }

    type Lang<T extends ASTNode> = {
        [K in T['type']]?: ASTNodeMatch<K>
    }

    type ASTNodeMatchReplaced<T> = Replace<T, ASTNode, Lang<ASTNode>>
    type ASTNodeMatch<T> = Omit<Extract<ASTNodeMatchReplaced<ASTNode>, { type: T }>, 'type'>

    const node: ASTNode = { type: 'Literal', value: "hello" }
    const node2: Lang<ASTNode> = { Literal: { value: "string" } }
    const node3: Lang<ASTNode> = { BinOp: { op: "+", lhs: node2, rhs: node2 } }
}

Going from Lang to a Descriminated Union Type:

namespace OrAnother {
    /* type ASTNode =
        { type: 'Literal', value: string | number | boolean } |
        { type: 'BinOp', op: string, lhs: ASTNode, rhs: ASTNode } |
        { type: 'UnOp', op: string, arg: ASTNode }
    */

    type Lang = {
        Literal?: { value: string | number | boolean },
        BinOp?: { op: string, lhs: Lang, rhs: Lang },
        UnOp?: { op: string, arg: Lang },
    } 

    type Replace<T, A> = {
        [P in keyof T]: T[P] extends A ? ASTNode : T[P]
    }

    type Pairs<T> = { [TKey in keyof T]: { type: TKey } & Replace<T[TKey], T> }
    type ASTNode = Pairs<Lang>[keyof Lang]

    const a1: ASTNode = { type: 'Literal', value: "dsda" }
    const a2: ASTNode = { type: 'BinOp', op: "+", lhs: a1, rhs: a1 }

    // These produce Type Errors (as expected)
    const a4: ASTNode = { type: 'BinOp', op: "+", lhs: 3, rhs: a1 } 
    const a5: ASTNode = { type: 'Literal', op: "-" }
}

Upvotes: 2

Related Questions