访问者模式

┌─────────────────────────────────────────────────────────────┐
│                    双分派执行流程                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Client                                                     │
│    │                                                        │
│    │ element.accept(visitor)                                │
│    ▼                                                        │
│  ┌──────────────────────────────────────────────┐           │
│  │  第一次分派：根据 Element 运行时类型          │           │
│  │  ConcreteElementA.accept(visitor)             │           │
│  │      │                                        │           │
│  │      │ visitor.visit(this)                    │           │
│  │      ▼                                        │           │
│  │  第二次分派：根据 this 编译时类型             │           │
│  │  ConcreteVisitor.visit(elementA: ElementA)    │           │
│  └──────────────────────────────────────────────┘           │
│                                                             │
│  结果：两次分派共同确定了最终执行的方法                     │
│                                                             │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                    角色协作关系                             │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  ObjectStructure                                            │
│    │                                                        │
│    │ 遍历 elements                                          │
│    ▼                                                        │
│  ┌───────────┐    ┌───────────┐                            │
│  │ Element A │    │ Element B │                            │
│  └─────┬─────┘    └─────┬─────┘                            │
│        │ accept(v)       │ accept(v)                       │
│        ▼                 ▼                                  │
│  ┌─────────────────────────────────────┐                   │
│  │           Visitor                   │                   │
│  ├─────────────────────────────────────┤                   │
│  │ + visitA(elementA) ── 操作 ElementA │                   │
│  │ + visitB(elementB) ── 操作 ElementB │                   │
│  └─────────────────────────────────────┘                   │
│                                                             │
│  新增操作：只需新增 ConcreteVisitor，无需修改 Element       │
│  新增元素：需修改所有 Visitor 接口和实现                    │
│                                                             │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                    适用性决策矩阵                           │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  元素类型稳定 & 操作频繁变化 ── 强烈推荐使用访问者模式     │
│                                                             │
│  元素类型稳定 & 操作稳定 ── 访问者模式可能过度设计         │
│                                                             │
│  元素类型频繁变化 & 操作稳定 ── 不推荐，改用策略模式       │
│                                                             │
│  元素类型频繁变化 & 操作频繁变化 ── 不推荐，考虑重构       │
│                                                             │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                    访问者模式要点总结                       │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  核心机制                                                    │
│  - 双分派：element.accept(v) -> v.visit(this)               │
│  - 第一次分派确定 Element 具体类型                          │
│  - 第二次分派确定 Visitor 中对应的 visit 方法               │
│                                                             │
│  使用时机                                                    │
│  - Element 类型稳定，操作频繁扩展                           │
│  - 需要跨多种 Element 类型执行操作                          │
│  - 不愿为新增操作修改 Element 类                            │
│                                                             │
│  注意事项                                                    │
│  - 新增 Element 类型需修改所有 Visitor                      │
│  - Visitor 可能需要访问 Element 内部状态                    │
│  - 递归结构中 Visitor 需自行处理遍历逻辑                    │
│  - TypeScript 中可用 Discriminated Union + never 实现穷尽检查│
│                                                             │
│  前端典型应用                                                │
│  - TypeScript Compiler: ts.visitEachChild                   │
│  - ESLint 规则：每个 Rule 是一个 Visitor                    │
│  - Babel 插件：visitor 对象定义节点变换                     │
│  - JSON Schema 校验：校验器遍历 Schema 结构                 │
│                                                             │
└─────────────────────────────────────────────────────────────┘

// ============================================================
// 基础实现：AST 节点访问器
// ============================================================

// --- Element 接口 ---

interface ASTNode {
  accept<T>(visitor: ASTVisitor<T>): T;
}

// --- Visitor 接口 ---
interface ASTVisitor<T> {
  visitNumber(node: NumberNode): T;
  visitBinaryExpr(node: BinaryExpressionNode): T;
}

// --- ConcreteElement ---
class NumberNode implements ASTNode {
  constructor(public readonly value: number) {}
  accept<T>(visitor: ASTVisitor<T>): T { return visitor.visitNumber(this); }
}

class BinaryExpressionNode implements ASTNode {
  constructor(
    public readonly op: '+' | '-' | '*' | '/',
    public readonly left: ASTNode,
    public readonly right: ASTNode
  ) {}
  accept<T>(visitor: ASTVisitor<T>): T { return visitor.visitBinaryExpr(this); }
}

// --- ObjectStructure ---
class ASTProgram {
  private nodes: ASTNode[] = [];
  add(node: ASTNode): this { this.nodes.push(node); return this; }
  accept<T>(visitor: ASTVisitor<T>): T[] { return this.nodes.map((node) => node.accept(visitor)); }
}

// --- ConcreteVisitor1: 求值 ---
class EvaluatorVisitor implements ASTVisitor<number> {
  visitNumber(node: NumberNode): number { return node.value; }
  visitBinaryExpr(node: BinaryExpressionNode): number {
    const left = node.left.accept(this);
    const right = node.right.accept(this);
    switch (node.op) {
      case '+': return left + right;
      case '-': return left - right;
      case '*': return left * right;
      case '/': return left / right;
    }
  }
}

// --- ConcreteVisitor2: 打印 ---
class PrinterVisitor implements ASTVisitor<string> {
  visitNumber(node: NumberNode): string { return String(node.value); }
  visitBinaryExpr(node: BinaryExpressionNode): string {
    return `(${node.left.accept(this)} ${node.op} ${node.right.accept(this)})`;
  }
}

// --- 使用 ---
const evaluator = new EvaluatorVisitor();
const printer = new PrinterVisitor();
const expression = new BinaryExpressionNode('*',
  new BinaryExpressionNode('+', new NumberNode(1), new NumberNode(2)),
  new NumberNode(3)
);

const program = new ASTProgram();
program.add(new NumberNode(42));
program.add(expression);

console.log(program.accept(evaluator)); // [42, 9]
console.log(program.accept(printer));   // ['42', '((1 + 2) * 3)']

// ============================================================
// 泛型访问者
// ============================================================

// 节点类型枚举
enum ASTNodeType {
  Number = 'Number',
  BinaryExpression = 'BinaryExpression',
  Identifier = 'Identifier',
  CallExpression = 'CallExpression',
}

// 泛型访问者接口：TNode 输入类型，TResult 返回类型
interface TypedVisitor<TResult> {
  visit(node: { type: ASTNodeType; [key: string]: unknown }): TResult;
}

// 具体访问者：类型检查器
class TypeCheckerVisitor implements TypedVisitor<string> {
  visit(node: { type: ASTNodeType; [key: string]: unknown }): string {
    switch (node.type) {
      case ASTNodeType.Number: return 'number';
      case ASTNodeType.Identifier: return 'unknown';
      case ASTNodeType.BinaryExpression: return 'number';
      case ASTNodeType.CallExpression: return 'number';
      default: return 'void';
    }
  }
}

// 使用
const checker = new TypeCheckerVisitor();
const callNode = {
  type: ASTNodeType.CallExpression,
  callee: { type: ASTNodeType.Identifier, name: 'add' },
  args: [
    { type: ASTNodeType.Identifier, name: 'x' },
    { type: ASTNodeType.Number, value: 1 },
  ],
};

console.log(checker.visit(callNode)); // 'number'

// ============================================================
// Discriminated Union + 类型收窄
// ============================================================

// 节点 Discriminated Union 定义
type ExprNode =
  | { kind: 'number'; value: number }
  | { kind: 'binary'; op: '+' | '-' | '*' | '/'; left: ExprNode; right: ExprNode }
  | { kind: 'conditional'; condition: ExprNode; then: ExprNode; else: ExprNode }
  | { kind: 'unary'; op: '-' | '!'; operand: ExprNode };

// 穷尽检查辅助函数：确保 switch 覆盖所有分支
function assertNever(x: never): never {
  throw new Error(`Unexpected node: ${JSON.stringify(x)}`);
}

// 求值访问者
function evaluateExpr(node: ExprNode): number {
  switch (node.kind) {
    case 'number': return node.value;
    case 'binary':
      const left = evaluateExpr(node.left);
      const right = evaluateExpr(node.right);
      switch (node.op) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/': return left / right;
      }
    case 'conditional':
      return evaluateExpr(node.condition) ? evaluateExpr(node.then) : evaluateExpr(node.else);
    case 'unary':
      if (node.op === '-') return -evaluateExpr(node.operand);
      return evaluateExpr(node.operand) ? 0 : 1;
    default: return assertNever(node);
  }
}

// 字符串化访问者
function stringifyExpr(node: ExprNode): string {
  switch (node.kind) {
    case 'number': return String(node.value);
    case 'binary': return `(${stringifyExpr(node.left)} ${node.op} ${stringifyExpr(node.right)})`;
    case 'conditional': return `${stringifyExpr(node.condition)} ? ${stringifyExpr(node.then)} : ${stringifyExpr(node.else)}`;
    case 'unary': return `${node.op}${stringifyExpr(node.operand)}`;
    default: return assertNever(node);
  }
}

// 使用
const expr: ExprNode = {
  kind: 'conditional',
  condition: { kind: 'unary', op: '!', operand: { kind: 'number', value: 0 } },
  then: { kind: 'binary', op: '+', left: { kind: 'number', value: 1 }, right: { kind: 'number', value: 2 } },
  else: { kind: 'number', value: 0 },
};

console.log(evaluateExpr(expr));   // 3
console.log(stringifyExpr(expr));  // !0 ? (1 + 2) : 0

// ============================================================
// 函数式访问者
// ============================================================

type FuncNode =
  | { kind: 'number'; value: number }
  | { kind: 'add'; left: FuncNode; right: FuncNode }
  | { kind: 'multiply'; left: FuncNode; right: FuncNode };

// 通用 transform 函数：接收一个部分访问者映射，返回变换后的节点
type PartialVisitor<T> = {
  [K in FuncNode['kind']]?: (node: Extract<FuncNode, { kind: K }>) => T;
};

function visit<T>(node: FuncNode, visitor: PartialVisitor<T>): T {
  const fn = visitor[node.kind];
  if (!fn) throw new Error(`未处理的节点类型: ${node.kind}`);
  return (fn as (n: FuncNode) => T)(node);
}

// 求值
const evaluate = (node: FuncNode): number => visit<number>(node, {
  number: (n) => n.value,
  add: (n) => evaluate(n.left) + evaluate(n.right),
  multiply: (n) => evaluate(n.left) * evaluate(n.right),
});

// 深度
const depth = (node: FuncNode): number => visit<number>(node, {
  number: () => 1,
  add: (n) => 1 + Math.max(depth(n.left), depth(n.right)),
  multiply: (n) => 1 + Math.max(depth(n.left), depth(n.right)),
});

// 常量折叠
const constantFold = (node: FuncNode): FuncNode => visit<FuncNode>(node, {
  number: (n) => n,
  add: (n) => {
    const left = constantFold(n.left);
    const right = constantFold(n.right);
    return left.kind === 'number' && right.kind === 'number'
      ? { kind: 'number', value: left.value + right.value }
      : { kind: 'add', left, right };
  },
  multiply: (n) => {
    const left = constantFold(n.left);
    const right = constantFold(n.right);
    return left.kind === 'number' && right.kind === 'number'
      ? { kind: 'number', value: left.value * right.value }
      : { kind: 'multiply', left, right };
  },
});

// 使用
const expr2: FuncNode = {
  kind: 'add',
  left: { kind: 'multiply', left: { kind: 'number', value: 2 }, right: { kind: 'number', value: 3 } },
  right: { kind: 'number', value: 4 },
};

console.log(evaluate(expr2));     // 10
console.log(depth(expr2));        // 3
console.log(constantFold(expr2)); // { kind: 'number', value: 10 }

// ============================================================
// 扩展实现：带状态与组合的访问者
// ============================================================

// 文件系统节点
interface FSNode {
  accept<T>(visitor: FSVisitor<T>): T;
}

class FileNode implements FSNode {
  constructor(
    public readonly name: string,
    public readonly size: number
  ) {}
  accept<T>(visitor: FSVisitor<T>): T { return visitor.visitFile(this); }
}

class DirectoryNode implements FSNode {
  private children: FSNode[] = [];
  constructor(public readonly name: string) {}
  add(node: FSNode): this { this.children.push(node); return this; }
  getChildren(): FSNode[] { return this.children; }
  accept<T>(visitor: FSVisitor<T>): T { return visitor.visitDirectory(this); }
}

// Visitor 接口
interface FSVisitor<T> {
  visitFile(file: FileNode): T;
  visitDirectory(dir: DirectoryNode): T;
}

// 访问者1：计算总大小
class SizeVisitor implements FSVisitor<number> {
  visitFile(file: FileNode): number { return file.size; }
  visitDirectory(dir: DirectoryNode): number {
    return dir.getChildren().reduce((sum, child) => sum + child.accept(this), 0);
  }
}

// 访问者2：打印树形结构
class PrintVisitor implements FSVisitor<string> {
  constructor(private indent = 0) {}
  visitFile(file: FileNode): string {
    return `${'  '.repeat(this.indent)}- ${file.name} (${file.size}KB)`;
  }
  visitDirectory(dir: DirectoryNode): string {
    const lines = [`${'  '.repeat(this.indent)}+ ${dir.name}/`];
    const visitor = new PrintVisitor(this.indent + 1);
    dir.getChildren().forEach((child) => lines.push(child.accept(visitor)));
    return lines.join('\n');
  }
}

// 使用
const root = new DirectoryNode('src');
const utils = new DirectoryNode('utils');
utils.add(new FileNode('helpers.ts', 3)).add(new FileNode('math.ts', 2));
const components = new DirectoryNode('components');
components.add(new FileNode('Button.tsx', 8)).add(new FileNode('Input.tsx', 6));
root.add(utils).add(components).add(new FileNode('index.ts', 1));

console.log(root.accept(new PrintVisitor()));
// + src/
//   + utils/
//     - helpers.ts (3KB)
//     - math.ts (2KB)
//   + components/
//     - Button.tsx (8KB)
//     - Input.tsx (6KB)
//   - index.ts (1KB)
console.log(`总大小: ${root.accept(new SizeVisitor())}KB`);

// TypeScript Compiler API 中的访问者模式
import * as ts from 'typescript';

// 自定义 Transformer：将所有标识符转为大写
function uppercaseTransformer(context: ts.TransformationContext): ts.Transformer<ts.SourceFile> {
  return (sourceFile: ts.SourceFile) => {
    // Visitor 函数：对每种节点类型定义变换逻辑
    function visitor(node: ts.Node): ts.Node {
      if (ts.isIdentifier(node)) {
        // 对 Identifier 节点执行变换
        return ts.factory.createIdentifier(node.text.toUpperCase());
      }
      // 递归访问子节点
      return ts.visitEachChild(node, visitor, context);
    }
    return ts.visitNode(sourceFile, visitor) as ts.SourceFile;
  };
}

// ESLint 规则本质上是 Visitor
// 简化的类型定义与规则结构（示意）
interface RuleContext {
  report(info: { node: unknown; message: string }): void;
}
type ASTVisitor = Record<string, (node: any) => void>;

interface ESLintRule {
  create(context: RuleContext): ASTVisitor;
}

// 示例：禁止使用 console.log 的规则
const noConsoleLogRule: ESLintRule = {
  create(context) {
    return {
      // visit CallExpression 节点
      CallExpression(node) {
        if (
          node.callee.type === 'MemberExpression' &&
          node.callee.object.type === 'Identifier' &&
          node.callee.object.name === 'console' &&
          node.callee.property.type === 'Identifier' &&
          node.callee.property.name === 'log'
        ) {
          context.report({
            node,
            message: 'Unexpected console.log call.',
          });
        }
      },
    };
  },
};

// Babel 插件中的 Visitor
import type { PluginObject } from '@babel/core';

const arrowFunctionPlugin: PluginObject = {
  name: 'transform-arrow-functions',
  visitor: {
    // 访问 ArrowFunctionExpression 节点
    ArrowFunctionExpression(path) {
      // 将箭头函数转换为普通函数
      const { node } = path;
      if (!node.body.type.endsWith('Expression')) {
        return; // 函数体已是块语句，无需转换
      }

      // 将表达式体的箭头函数转换为普通函数（Babel 内置转换能力）
      path.arrowFunctionToExpression();
    },
  },
};

// JSON Schema 校验器作为 Visitor
interface SchemaNode {
  type?: string;
  properties?: Record<string, SchemaNode>;
  items?: SchemaNode;
  required?: string[];
  minimum?: number;
  maximum?: number;
  [key: string]: unknown;
}

interface SchemaVisitor<T> {
  visitObject(schema: SchemaNode, data: Record<string, unknown>): T;
  visitArray(schema: SchemaNode, data: unknown[]): T;
  visitString(schema: SchemaNode, data: string): T;
  visitNumber(schema: SchemaNode, data: number): T;
  visitBoolean(schema: SchemaNode, data: boolean): T;
  visitType(schema: SchemaNode, data: unknown): T;
}

// 具体访问者：JSON Schema 校验器
class SchemaValidator implements SchemaVisitor<boolean> {
  visitObject(schema: SchemaNode, data: Record<string, unknown>): boolean {
    if (!schema.properties) return true;
    return Object.entries(schema.properties).every(([key, childSchema]) =>
      key in data ? this.visitType(childSchema, data[key]) : !schema.required?.includes(key)
    );
  }
  visitArray(schema: SchemaNode, data: unknown[]): boolean {
    const items = schema.items;
    if (!items) return true;
    return data.every((item) => this.visitType(items, item));
  }
  visitString(_schema: SchemaNode, _data: string): boolean { return true; }
  visitNumber(schema: SchemaNode, data: number): boolean {
    if (schema.minimum !== undefined && data < schema.minimum) return false;
    if (schema.maximum !== undefined && data > schema.maximum) return false;
    return true;
  }
  visitBoolean(_schema: SchemaNode, _data: boolean): boolean { return true; }
  visitType(schema: SchemaNode, data: unknown): boolean {
    switch (schema.type) {
      case 'object':
        return this.visitObject(schema, data as Record<string, unknown>);
      case 'array':
        return this.visitArray(schema, data as unknown[]);
      case 'string':
        return this.visitString(schema, data as string);
      case 'number':
        return this.visitNumber(schema, data as number);
      case 'boolean':
        return this.visitBoolean(schema, data as boolean);
      default:
        return true;
    }
  }
}

// 解释器模式：操作内嵌在元素中
interface Expr {
  interpret(): number;
}

class AddExpr implements Expr {
  constructor(private left: Expr, private right: Expr) {}
  interpret(): number {
    return this.left.interpret() + this.right.interpret();
  }
}

// 访问者模式：操作与元素分离
interface ExprNode3 {
  accept<T>(v: ExprVisitor3<T>): T;
}

interface ExprVisitor3<T> {
  visitNum(node: NumNode): T;
  visitAdd(node: AddNode3): T;
}

class AddNode3 implements ExprNode3 {
  constructor(public left: ExprNode3, public right: ExprNode3) {}
  accept<T>(v: ExprVisitor3<T>): T { return v.visitAdd(this); }
}

class NumNode implements ExprNode3 {
  constructor(public value: number) {}
  accept<T>(v: ExprVisitor3<T>): T {
    return v.visitNum(this);
  }
}

// 求值访问者：新增操作无需修改节点类
class EvalVisitor3 implements ExprVisitor3<number> {
  visitNum(node: NumNode): number { return node.value; }
  visitAdd(node: AddNode3): number { return node.left.accept(this) + node.right.accept(this); }
}

// 组合模式 + 访问者模式配合
// 组合模式定义树形结构，访问者模式定义对树的操作

interface Shape {
  accept<T>(visitor: ShapeVisitor<T>): T;
}

class Circle implements Shape {
  constructor(public radius: number) {}
  accept<T>(visitor: ShapeVisitor<T>): T {
    return visitor.visitCircle(this);
  }
}

class Rectangle implements Shape {
  constructor(public width: number, public height: number) {}
  accept<T>(visitor: ShapeVisitor<T>): T {
    return visitor.visitRectangle(this);
  }
}

// Composite：图形组
class Group implements Shape {
  constructor(public shapes: Shape[]) {}
  accept<T>(visitor: ShapeVisitor<T>): T {
    return visitor.visitGroup(this);
  }
}

interface ShapeVisitor<T> {
  visitCircle(c: Circle): T;
  visitRectangle(r: Rectangle): T;
  visitGroup(g: Group): T;
}

// 面积访问者
class AreaVisitor implements ShapeVisitor<number> {
  visitCircle(c: Circle): number { return Math.PI * c.radius * c.radius; }
  visitRectangle(r: Rectangle): number {
    return r.width * r.height;
  }
  visitGroup(g: Group): number {
    return g.shapes.reduce((sum, s) => sum + s.accept(this), 0);
  }
}

// 元素接口：接受访问者（双重分派入口）
interface Element {
    void accept(Visitor visitor);
}

// 具体元素：文件
class File implements Element {
    private final String name;
    private final int size;

    public File(String name, int size) {
        this.name = name;
        this.size = size;
    }

    public String getName() { return name; }
    public int getSize() { return size; }

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);  // 把自身传给访问者（触发第二次分派）
    }
}

// 具体元素：目录
class Directory implements Element {
    private final String name;

    public Directory(String name) {
        this.name = name;
    }

    public String getName() { return name; }

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);  // 第二次分派到具体 visit 重载
    }
}

// 访问者接口：每种元素对应一个 visit 重载
interface Visitor {
    void visit(File file);
    void visit(Directory directory);
}

// 具体访问者：打印信息（新增操作无需修改 Element）
class PrintVisitor implements Visitor {
    @Override
    public void visit(File file) {
        System.out.println("文件: " + file.getName() + " (" + file.getSize() + "B)");
    }

    @Override
    public void visit(Directory directory) {
        System.out.println("目录: " + directory.getName());
    }
}

// 使用
public class Client {
    public static void main(String[] args) {
        Element[] elements = {
                new File("a.txt", 100),
                new Directory("src")
        };
        Visitor printer = new PrintVisitor();
        for (Element element : elements) {
            element.accept(printer);  // 双重分派
        }
    }
}

from abc import ABC, abstractmethod

class Element(ABC):
    @abstractmethod
    def accept(self, visitor: "Visitor"):
        pass

class File(Element):
    def __init__(self, name: str, size: int):
        self.name = name
        self.size = size

    def accept(self, visitor: "Visitor"):
        visitor.visit_file(self)

class Directory(Element):
    def __init__(self, name: str):
        self.name = name

    def accept(self, visitor: "Visitor"):
        visitor.visit_directory(self)

class Visitor(ABC):
    @abstractmethod
    def visit_file(self, file: File):
        pass

    @abstractmethod
    def visit_directory(self, directory: Directory):
        pass

class PrintVisitor(Visitor):
    def visit_file(self, file: File):
        print(f"文件: {file.name} ({file.size}B)")

    def visit_directory(self, directory: Directory):
        print(f"目录: {directory.name}")

elements = [File("a.txt", 100), Directory("src")]
printer = PrintVisitor()
for element in elements:
    element.accept(printer)