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

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

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 的表示更改为其他内容。

抱歉冗长 post。提前致谢。

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 可以自己找出空白。

Answer 2

我找到了解决方案：

首先，我重写了通道，所以没有通道是向现有节点属性添加属性，只是添加节点。

然后，我使 ASTVisitor class 占用额外的节点：

abstract class ASTVisitor<InputExprAddition, OutputExprAddition> { }

现在，每个节点都有一个方法，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>;

TypeScript 中的递归 AST 访问者

Recursive AST visitor in TypeScript

visitor-pattern

typescript