Vizitator recursiv AST în TypeScript

În prezent scriu un parser. Parserul produce un AST, iar apoi îl parcurg folosind diverse treceri. AST-ul este (simplificat):

type LiteralExpr = {
  readonly kind: 'literal',
  readonly value: number,
};
type UnaryExpr = {
  readonly kind: 'unary',
  readonly operator: '!' | '-',
  readonly operand: Expr,
};
type BinaryExpr = {
  readonly kind: 'binary',
  readonly left: Expr,
  readonly operator: '+' | '-' | '*' | '/',
  readonly right: Expr,
};
/** Parenthesized expression */
type GroupingExpr = {
  readonly kind: 'grouping',
  readonly subExpr: Expr,
};
type Expr = LiteralExpr | UnaryExpr | BinaryExpr | GroupingExpr;

Fiecare trecere modifică puțin AST-ul, producând un AST nou. De exemplu, am o trecere care elimină nodurile grouping:

class ParensRemover {
  doPass(expr: Expr): Expr {
    switch (expr.kind) {
      case 'literal': return expr;
      case 'unary': return { ...expr, operand: this.doPass(expr.operand) };
      case 'binary': return { ...expr, left: this.doPass(expr.left), right: this.doPass(expr.right) };
      case 'grouping': return this.doPass(expr.subExpr);
    }
  }
}

Totuși, acest cod devine repede unul redundant, mai ales când am o mulțime de noduri, așa că aș dori să îl refactorizez într-o clasă recursivă de bază folosind modelul vizitator:

abstract class ASTVisitor {
  doPass(expr: Expr): Expr {
    switch (expr.kind) {
      case 'literal': return this.visitLiteral(expr);
      case 'unary': return this.visitUnary(expr);
      case 'binary': return this.visitBinary(expr);
      case 'grouping': return this.visitGrouping(expr);
    }
  }

  protected visitLiteral(expr: LiteralExpr): Expr {
    return expr;
  }
  protected visitUnary(expr: UnaryExpr): Expr {
    return { ...expr, operand: this.doPass(expr.operand) };
  }
  protected visitBinary(expr: BinaryExpr): Expr {
    return { ...expr, left: this.doPass(expr.left), right: this.doPass(expr.right) };
  }
  protected visitGrouping(expr: GroupingExpr): Expr {
    return { ...expr, subExpr: this.doPass(expr.subExpr) };
  }
}

class ParensRemover extends ASTVisitor {
  protected visitGrouping(expr: GroupingExpr): Expr {
    return this.doPass(expr.subExpr);
  }
}

Până acum totul bine. Problema cu acest cod este că următoarele treceri după ParensRemover vor trebui să se ocupe de tipul de nod grouping, deși, desigur, nu vor exista noduri de acest fel. Acesta poate să nu pară o problemă mare, dar am multe tipuri de noduri și multe treceri, aproape fiecare dintre ele modifică ușor AST-ul - elimină noduri sau adaugă altele, sau schimbă tipul unei proprietăți. Așa că am schimbat tipul AST Expr în următorul mod:

type LiteralExpr = {
  readonly kind: 'literal',
  readonly value: number,
};
type UnaryExpr<Addition> = {
  readonly kind: 'unary',
  readonly operator: '!' | '-',
  readonly operand: ExprBase<Addition>,
};
type BinaryExpr<Addition> = {
  readonly kind: 'binary',
  readonly left: ExprBase<Addition>,
  readonly operator: '+' | '-' | '*' | '/',
  readonly right: ExprBase<Addition>,
};
/** Parenthesized expression */
type GroupingExpr = {
  readonly kind: 'grouping',
  readonly subExpr: BeforeRemoveParensExpr,
};
type ExprBase<Addition> = LiteralExpr | UnaryExpr | BinaryExpr | Addition;
type BeforeRemoveParensExpr = ExprBase<GroupingExpr>;
type AfterRemoveParensExpr = ExprBase<never>;

Dar acum cum va ști ASTVisitor tipul corect? Am încercat următoarele:

type AllExprs = BeforeRemoveParensExpr | AfterRemoveParensExpr;

type PickExpr<E extends AllExprs, K extends E['kind']> = /* details not important, this type pulls a specific kind out of Expr */;

abstract class ASTVisitor<InputExpr extends AllExprs, OutputExpr extends AllExprs> {
  doPass(expr: InputExpr): OutputExpr {
    switch (expr.kind) {
      case 'literal': return this.visitLiteral(expr as any);
      case 'unary': return this.visitUnary(expr as any);
      case 'binary': return this.visitBinary(expr as any);
      case 'grouping': return this.visitGrouping(expr as any);
    }
  }

  protected visitLiteral(expr: PickExpr<InputExpr, 'literal'>) {
    return expr as unknown OutputExpr;
  }
  protected visitUnary(expr: PickExpr<InputExpr, 'unary'>) {
    return { ...expr, operand: this.doPass(expr.operand) } as unknown as OutputExpr;
  }
  protected visitBinary(expr: PickExpr<InputExpr, 'binary'>) {
    return { ...expr, left: this.doPass(expr.left), right: this.doPass(expr.right) } as unknown as OutputExpr;
  }
  protected visitGrouping(expr: PickExpr<InputExpr, 'grouping'>) {
    return { ...expr, subExpr: this.doPass(expr.subExpr) } as unknown as OutputExpr;
  }
}

class ParensRemover extends ASTVisitor<BeforeRemoveParensExpr, AfterRemoveParensExpr> {
  protected visitGrouping(expr: GroupingExpr): AfterRemoveParensExpr {
    return this.doPass(expr.subExpr);
  }
}

Dar nu sunt mulțumit de această soluție. În afară de numeroasele conversii la any în ASTVisitor, se pierde siguranța tipurilor. Dacă uit să suprascriu un visitX() pentru X care ar trebui să se schimbe între treceri, nu voi primi erori de compilare și în schimb programul va eșua undeva într-un mod bizar.

Pot să fac ce vreau fără să pierd siguranța pe care o oferă TypeScript? Pot schimba reprezentarea AST într-altceva, dacă este necesar.

Îmi pare rău pentru mesajul lung. Mulțumesc anticipat.

Răspuns #1

Se pare că cauți tipul utilitar Exclude<Type, ExcludedUnion>.
La bază, tipul este foarte simplu:

type Foo = A | B | C;
type Bar = Exclude<Foo, A>; // Equal to B | C

Deși s-ar putea să fie nevoie să îți restructurezi codul pentru a accepta diferitele ieșiri și intrări într-un mod rezonabil, ai putea apoi să-ți tipizezi funcțiile astfel încât:

function visitGrouping(expr: Expr): Exclude<Expr, GroupingExpr> { ... }

function doPass(expr: Expr) {
  switch (expr.kind) {
    case 'grouping': return visitGrouping(expr);
    // ...
  }
}

În acest caz, Typescript poate completa singur golurile.

Răspunsul #2

Am găsit o soluție:

Mai întâi, rescriu trecerile astfel încât nicio trecere să nu adauge proprietăți unui nod existent, ci doar să adauge noduri.

Apoi, am făcut ca clasa ASTVisitor să preia nodurile suplimentare:

abstract class ASTVisitor<InputExprAddition, OutputExprAddition> {
}

Și acum, am o metodă pentru fiecare nod și o metodă suplimentară pentru ExprAddition:

doPass(expr: ExprBase<InputExprAddition>): ExprBase<OutputExprAddition> {
  switch (expr.kind) {
    case 'literal': return this.visitLiteral(expr);
    // ...
    default: return this.visitAddition(expr);
  }
}
protected visitLiteral(literal: LiteralExpr<InputExprAddition>): ExprBase<OutputExprAddition> {
  return literal;
}
// ...
protected abstract visitAddition(expr: InputExprAddition): ExprBase<OutputExprAddition>;