name: pattern-matching description: 实现模式匹配的专家技能，包括穷举性检查、决策树编译和高效的匹配分发代码生成。 allowed-tools: Read, Write, Edit, Bash, Glob, Grep

模式匹配技能

为编程语言实现模式匹配，包括穷举性检查、有用性分析和高效编译到决策树。

能力

解析模式语法（构造器、通配符、绑定、字面量）
实现穷举性和有用性检查
将模式编译为决策树
实现守卫子句处理
设计或模式（or-patterns）和别名模式（as-patterns）
实现嵌套模式匹配
优化模式匹配覆盖率
生成高效的匹配分发代码

使用场景

在以下情况时调用此技能：

为语言添加模式匹配功能
实现穷举性检查
高效编译模式
处理复杂的模式特性

输入参数

参数	类型	必填	描述
patternTypes	数组	是	支持的模式类型
targetLanguage	字符串	是	实现的目标语言
compilationStrategy	字符串	否	编译策略（决策树、回溯）
features	数组	否	要实现的进阶功能

模式类型

{
  "patternTypes": [
    "wildcard",
    "variable",
    "literal",
    "constructor",
    "tuple",
    "record",
    "list",
    "or-pattern",
    "as-pattern",
    "guard"
  ]
}

功能选项

{
  "features": [
    "exhaustiveness-checking",
    "usefulness-checking",
    "decision-tree-compilation",
    "guard-clauses",
    "nested-patterns",
    "view-patterns",
    "active-patterns"
  ]
}

输出结构

pattern-matching/
├── syntax/
│   ├── pattern.grammar            # 模式语法
│   └── match-expr.grammar         # 匹配表达式语法
├── analysis/
│   ├── exhaustiveness.ts          # 穷举性检查器
│   ├── usefulness.ts              # 有用性/冗余性检查器
│   └── pattern-types.ts           # 模式类型推断
├── compilation/
│   ├── decision-tree.ts           # 决策树构建器
│   ├── code-generator.ts          # 代码生成器
│   └── optimizer.ts               # 模式优化器
├── runtime/
│   ├── matcher.ts                 # 运行时匹配（解释器）
│   └── guards.ts                  # 守卫求值
└── tests/
    ├── exhaustiveness.test.ts
    ├── compilation.test.ts
    └── runtime.test.ts

模式语法

// 模式抽象数据类型
type Pattern =
  | { type: 'wildcard' }                              // _
  | { type: 'variable'; name: string }                // x
  | { type: 'literal'; value: Literal }               // 42, "hello", true
  | { type: 'constructor'; name: string; args: Pattern[] }  // Some(x), Cons(h, t)
  | { type: 'tuple'; elements: Pattern[] }            // (x, y, z)
  | { type: 'record'; fields: Map<string, Pattern> }  // { name: n, age: a }
  | { type: 'list'; elements: Pattern[]; rest?: Pattern }  // [x, y, ...rest]
  | { type: 'or'; patterns: Pattern[] }               // p1 | p2
  | { type: 'as'; pattern: Pattern; name: string }    // p as x
  | { type: 'guard'; pattern: Pattern; guard: Expr }; // p if cond

// 匹配表达式
interface MatchExpr {
  scrutinee: Expr;
  arms: MatchArm[];
}

interface MatchArm {
  pattern: Pattern;
  guard?: Expr;
  body: Expr;
}

穷举性检查

// 基于《模式匹配警告》（Maranget）

type PatternMatrix = Pattern[][];  // 行 = 分支，列 = 待匹配值

// 检查模式矩阵是否穷举
function isExhaustive(matrix: PatternMatrix, types: Type[]): boolean {
  if (matrix.length === 0) return false;
  if (types.length === 0) return true;

  const firstCol = matrix.map(row => row[0]);
  const sigma = getConstructorSignature(types[0]);

  if (sigma.isComplete(firstCol)) {
    // 所有构造器都存在 - 检查特化
    return sigma.constructors.every(ctor =>
      isExhaustive(specialize(matrix, ctor), specializationTypes(types, ctor))
    );
  } else {
    // 缺少某些构造器 - 检查默认矩阵
    return isExhaustive(defaultMatrix(matrix), types.slice(1));
  }
}

// 生成未覆盖情况的见证
function findUncoveredCase(matrix: PatternMatrix, types: Type[]): Pattern[] | null {
  if (matrix.length === 0) {
    // 空矩阵 - 任何值都未被覆盖
    return types.map(generateWildcard);
  }
  if (types.length === 0) return null;  // 穷举

  const sigma = getConstructorSignature(types[0]);
  const firstCol = matrix.map(row => row[0]);

  if (sigma.isComplete(firstCol)) {
    for (const ctor of sigma.constructors) {
      const witness = findUncoveredCase(
        specialize(matrix, ctor),
        specializationTypes(types, ctor)
      );
      if (witness) {
        return [applyConstructor(ctor, witness.slice(0, ctor.arity)), ...witness.slice(ctor.arity)];
      }
    }
    return null;
  } else {
    // 查找缺失的构造器
    const missing = sigma.constructors.find(c => !firstCol.some(p => matchesCtor(p, c)));
    if (missing) {
      return [generatePattern(missing), ...types.slice(1).map(generateWildcard)];
    }
    return findUncoveredCase(defaultMatrix(matrix), types.slice(1));
  }
}

决策树编译

// 用于高效匹配的决策树
type DecisionTree =
  | { type: 'fail' }
  | { type: 'leaf'; bindings: Map<string, Access>; body: Expr }
  | { type: 'switch'; access: Access; cases: SwitchCase[]; default?: DecisionTree };

interface SwitchCase {
  constructor: Constructor;
  tree: DecisionTree;
}

interface Access {
  root: string;
  path: AccessStep[];
}

type AccessStep =
  | { type: 'field'; index: number }
  | { type: 'deref' };

// 将模式编译为决策树
function compilePatterns(arms: MatchArm[], scrutinee: Access): DecisionTree {
  if (arms.length === 0) return { type: 'fail' };

  // 找到最佳拆分列（启发式）
  const column = selectColumn(arms);

  // 按该列的构造器对分支进行分组
  const groups = groupByConstructor(arms, column);

  if (groups.size === 0) {
    // 全是通配符 - 直接使用第一个分支
    const bindings = extractBindings(arms[0].pattern, scrutinee);
    return { type: 'leaf', bindings, body: arms[0].body };
  }

  // 构建switch节点
  const cases: SwitchCase[] = [];
  for (const [ctor, ctorArms] of groups) {
    const specializedAccess = extendAccess(scrutinee, ctor);
    cases.push({
      constructor: ctor,
      tree: compilePatterns(specializeArms(ctorArms, ctor), specializedAccess)
    });
  }

  const defaultArms = arms.filter(arm => isWildcard(arm.pattern, column));
  const defaultTree = defaultArms.length > 0
    ? compilePatterns(defaultArms, scrutinee)
    : undefined;

  return { type: 'switch', access: scrutinee, cases, default: defaultTree };
}

守卫子句处理

// 守卫使穷举性复杂化 - 我们必须保守处理
interface GuardedArm {
  pattern: Pattern;
  guard: Expr | null;
  body: Expr;
}

// 对于穷举性：将有守卫的模式视为可能失败
function exhaustivenessWithGuards(arms: GuardedArm[], types: Type[]): Warning[] {
  const warnings: Warning[] = [];

  // 移除守卫进行穷举性检查（保守）
  const unguardedMatrix = arms.map(arm => [arm.pattern]);
  if (!isExhaustive(unguardedMatrix, types)) {
    // 如果守卫覆盖了所有情况，可能仍然是穷举的
    // 但我们无法静态知道 - 发出警告
    warnings.push({
      type: 'possibly-non-exhaustive',
      message: '匹配可能不是穷举的（存在守卫）',
      suggestion: '考虑添加一个兜底模式'
    });
  }

  return warnings;
}

// 带守卫的决策树
type GuardedTree =
  | { type: 'fail' }
  | { type: 'guard'; test: Expr; success: GuardedTree; failure: GuardedTree }
  | { type: 'leaf'; bindings: Map<string, Access>; body: Expr }
  | { type: 'switch'; access: Access; cases: SwitchCase[]; default?: GuardedTree };

代码生成

// 从决策树生成代码
function generateCode(tree: DecisionTree, target: CodeTarget): Code {
  switch (tree.type) {
    case 'fail':
      return target.emitMatchFailure();

    case 'leaf':
      const setup = Array.from(tree.bindings.entries())
        .map(([name, access]) => target.emitBinding(name, access));
      return target.emitBlock([...setup, target.emitExpr(tree.body)]);

    case 'switch':
      return target.emitSwitch(
        target.emitAccess(tree.access),
        tree.cases.map(c => ({
          test: target.emitConstructorTest(c.constructor),
          body: generateCode(c.tree, target)
        })),
        tree.default ? generateCode(tree.default, target) : target.emitMatchFailure()
      );
  }
}

// Rust输出示例
function emitRustMatch(tree: DecisionTree): string {
  // 输入：match x { Some(y) => y + 1, None => 0 }
  // 输出：
  // match x {
  //   Some(ref __0) => {
  //     let y = __0;
  //     y + 1
  //   }
  //   None => 0
  // }
}

或模式和别名模式

// 或模式：如果任何子模式匹配则匹配
// (Red | Green | Blue) => "color"

function expandOrPattern(pattern: Pattern): Pattern[] {
  if (pattern.type === 'or') {
    return pattern.patterns.flatMap(expandOrPattern);
  }
  // 递归展开子模式
  // ...
  return [pattern];
}

// 别名模式：将整个匹配绑定到名称
// (x :: xs) as list => (list, x)

function handleAsPattern(
  pattern: AsPattern,
  access: Access,
  bindings: Map<string, Access>
): void {
  // 将名称绑定到当前访问路径
  bindings.set(pattern.name, access);
  // 继续处理内部模式
  extractBindings(pattern.pattern, access, bindings);
}

工作流程

定义模式语法 - 模式的文法
实现模式解析器 - 将模式解析为AST
构建穷举性检查器 - 基于矩阵的分析
添加有用性检查器 - 检测冗余模式
实现决策树编译 - 高效匹配
生成目标代码 - 从决策树生成
处理守卫 - 保守的守卫分析
编写测试 - 穷举性、编译、运行时

应用的最佳实践

带守卫的保守穷举性
信息丰富的非穷举性见证
高效的决策树编译
正确的绑定提取顺序
支持嵌套模式
清晰的冗余警告

参考文献

模式匹配警告（Maranget）：https://moscova.inria.fr/~maranget/papers/warn/
编译模式匹配：https://www.cs.tufts.edu/~nr/cs257/archive/luc-maranget/jun08.pdf
Rust模式匹配：https://doc.rust-lang.org/reference/patterns.html
OCaml模式匹配：https://ocaml.org/docs/pattern-matching

目标流程

pattern-matching-implementation.js
parser-development.js
code-generation-llvm.js
interpreter-implementation.js