typescript - TypeScript 中的递归 AST 访问者

Question

我目前正在编写解析器。解析器生成一个 AST，然后我使用各种遍历来处理它。 AST 是(简化的):

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;

每一遍都会稍微改变 AST，从而产生一个新的 AST。例如，我通过消除 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);
    }
  }
}

但是，这段代码很快就变成了样板文件，尤其是。当我有大量节点时，所以我想使用访问者模式将其重构为基本递归类:

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);
  }
}

到目前为止一切顺利。这段代码的问题在于，ParensRemover 之后的下一个过程将不得不处理节点类型 grouping，尽管当然不会有这种类型的节点。这可能看起来没什么大不了的，但我有很多种节点和很多遍，几乎每一个都稍微改变了 AST——删除节点或添加另一个节点，或者更改属性的类型。所以我将 AST Expr 类型更改为以下内容:

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>;

但是现在 ASTVisitor 如何知道正确的类型呢？我尝试了以下方法:

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);
  }
}

但我对这个解决方案并不满意。除了在 ASTVisitor 中对 any 的多次强制转换外，它失去了类型安全性。如果我忘记为 X 覆盖一个 visitX() ，它应该在两次之间改变，我不会得到编译器错误，而是程序会以一种奇怪的方式失败。

我可以做我想做的事而不失去 TypeScript 提供的安全性吗？如果需要，我可以将 AST 的表示更改为其他内容。

抱歉这篇文章太长了。提前致谢。

Answer 1

听起来您正在寻找 Exclude<Type, ExcludedUnion> utility type .
该类型的核心非常简单:

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

虽然您可能需要重组代码以合理地接受不同的输出和输入，但您可以这样输入您的函数:

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

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

在这种情况下，Typescript 可以自己找出空白。