# zigregex

**Repository Path**: graviton/zigregex

## Basic Information

- **Project Name**: zigregex
- **Description**: Regex in zig lang
- **Primary Language**: Unknown
- **License**: AGPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-11-03
- **Last Updated**: 2026-11-04

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# zigregex

用 Zig 0.17 编写的正则表达式库，无外部依赖，有两种方言：

- **`python`**（默认）：语法与匹配语义以 Python 3.14 `re` 为准。最初为 [typlint](https://gitee.com/graviton/typlint) 编写，以便规则可以直接照抄 Python 脚本里的正则。
- **`pcre2`**：PCRE2 10.50 UTF 模式的语法与语义，以 C 版 libpcre2 为参照逐项比对（见“测试”）。

两种方言共用同一套编译器和回溯 VM；另有可选的 Pike VM 引擎，对它支持的模式保证线性时间（见“引擎”）。

相关文档：

- 实现计划与进度：[docs/pcre2-rewrite-plan.md](docs/pcre2-rewrite-plan.md)；
- 递归、条件、回溯动词与部分匹配的设计：[docs/p2-design.md](docs/p2-design.md)；
- 性能优化与 Pike VM 的设计：[docs/perf-design.md](docs/perf-design.md)。

许可证：AGPL-3.0，见 [LICENSE](LICENSE)。

## Python 方言

- 字面量与转义：`\n \t \r \f \v \a`、`\xhh`、`\uhhhh`、`\Uhhhhhhhh`、八进制 `\0`、`\101`；
- `.`、字符类 `[...]`、`[^...]`、`\w \d \s` 及其否定 `\W \D \S`；
- 断言：`^ $ \A \Z \z \b \B`；
- 捕获组 `(…)`、非捕获组 `(?:…)`、命名组 `(?P<name>…)` / `(?<name>…)`、原子组 `(?>…)`；
- 分支 `|`；量词 `* + ? {m} {m,} {,n} {m,n}`，以及懒惰形式 `*?` 等、占有形式 `*+` 等；
- 前瞻 `(?=…)` `(?!…)`，定宽后顾 `(?<=…)` `(?<!…)`；
- 反向引用 `\1`、`(?P=name)`；
- 标志 `i m s`：编译选项、全局写法 `(?i)`（只能放在模式开头）、作用域写法 `(?i-s:…)`；注释 `(?#…)`；
- 替换模板（`Matcher.replace`）：`\1`、`\g<1>`、`\g<name>` 与 `re.sub` 的转义规则。

不支持：`x`/`a`/`L` 标志、条件子模式 `(?(1)…)`。

语义细节与 Python 3.14 一致，例如：
- `$` 也匹配末尾换行之前的位置；`\Z` 只匹配文本末尾；
- `\B` 可以匹配空串；
- 迭代中遇到空匹配后的处理与 `finditer` 相同；
- 大小写折叠包括 `s`/`ſ`、`k`/`K`（开尔文符号）这类额外等价；
- `\w \d \s` 与大小写折叠取自 Python 的 Unicode 数据（16.0）。

## PCRE2 方言

```zig
var re = try regex.Regex.compile(gpa, pattern, .{ .dialect = .pcre2, .ucp = true });
```

支持：

- 全部转义：`\x{…}` `\o{…}` `\cX` `\e` `\N{U+…}`、`\Q…\E`、`\h \H \v \V \R \N \X \K \G`、`\b \B \A \Z \z`；`\d \s \w` 默认 ASCII，`ucp` 时按 Unicode；
- Unicode 属性 `\p{…}` `\P{…}`：一般类别、脚本与脚本扩展（`sc:` `scx:`）、布尔属性、`bidi_class:`、`L&` `Xan` `Xps` `Xsp` `Xwd` `Xuc`；数据为 PCRE2 自带的 Unicode 17.0；
- 字符类：区间、POSIX 类 `[:alpha:]`（`ucp` 时按 Unicode）、`[[:<:]]` `[[:>:]]`；
- 选项：`i m s x xx n U J`、`(?^)`、`(?aD)` 等 ASCII 限制，可写在模式任意位置，作用到所在组结束；模式开头的 `(*UCP)` `(*CRLF)` `(*NOTEMPTY)` `(*NO_START_OPT)` `(*LIMIT_MATCH=n)` 等；
- 量词 `{,n}`、带空格的 `{ 1 , 3 }`、懒惰与占有形式，`U` 选项；
- 命名组的各种写法、重名组（`J`）、重复编号组 `(?|…)`；
- 反向引用 `\1` `\g{-1}` `\g1` `\k<n>` `\k'n'` `\k{n}` `(?P=n)`，前向引用；
- 原子组、前后顾（含字母写法 `(*pla:…)` 等），**变长后顾**（每个分支有界，变长时最长 255）；
- 递归与子程序调用：`(?R)` `(?1)` `(?-1)` `(?+1)` `(?&name)` `(?P>name)` `\g<1>` `\g'name'`；
- 条件子模式：`(?(1)…|…)`、`(?(<name>)…)`、`(?(R)…)`、`(?(R1)…)`、`(?(R&name)…)`、`(?(DEFINE)…)`、`(?(VERSION>=10.4)…)`、断言条件；
- 回溯控制动词：`(*ACCEPT)` `(*FAIL)` `(*COMMIT)` `(*PRUNE)` `(*SKIP)` `(*SKIP:NAME)` `(*THEN)` `(*MARK:NAME)`；`Match.mark` 与 `Matcher.lastMark()` 给出标记名；
- 换行约定 `lf cr crlf any anycrlf nul`，`\R` 的 `bsr_anycrlf`；
- 编译选项 `dollar_endonly` `literal` `anchored` `end_anchored` `allow_empty_class` `match_unset_backref` `alt_bsux` `no_start_optimize`；
- 匹配选项（`Matcher.exec`）：`anchored` `not_bol` `not_eol` `not_empty` `not_empty_atstart`，部分匹配 `partial = .soft / .hard`；
- 替换（`Matcher.replace`）：`$n` `${n}` `$name` `${name}` `$<name>` `$&` `` $` `` `$'` `$_` `$+` `${*MARK}`；`extended` 时还有转义、`\U \L \u \l \E`、`${n:-默认}` `${n:+有:无}`；以及 `literal` `unknown_unset` `unset_empty`；
- 模式信息 `Regex.patternInfo()`。

不支持（编译时报“not supported”）：callout `(?C…)`、`\C`、非原子断言 `(*napla:…)`、扫描子串 `(*scs:…)`、脚本连续 `(*sr:…)`、扩展字符类 `(?[…])`、调用时返回捕获组 `(?1(…))`、`(?r)` 与土耳其大小写选项；以及非 UTF 模式、16/32 位码元、DFA、JIT。

## 用法

添加依赖（会写入 `build.zig.zon` 的 `.url` 和 `.hash`）：

```sh
zig fetch --save=zigregex "git+https://gitee.com/graviton/zigregex.git#<commit>"
```

`build.zig`：

```zig
const regex = b.dependency("zigregex", .{ .target = target, .optimize = optimize }).module("regex");
exe.root_module.addImport("regex", regex);
```

代码：

```zig
const regex = @import("regex");

var diag: regex.Diagnostics = .{};
var re = try regex.Regex.compile(gpa, "(?P<user>\\w+)@(\\w+)", .{ .diagnostics = &diag });
defer re.deinit();

var m = try regex.Matcher.init(gpa, &re, .{}); // 可复用，避免每次分配
defer m.deinit();

if (try m.search(input, 0)) |hit| {
    _ = hit.group(re.groupIndex("user").?); // ?[]const u8
}
var it = m.iterator(input); // finditer / 全局匹配
while (try it.next()) |hit| _ = hit.span(0);

const out = try m.replaceAlloc(gpa, input, "\\2:\\1", .{}); // re.sub
defer gpa.free(out);
```

- 位置是 UTF-8 字节偏移；匹配按码点进行，非法 UTF-8 按单字节处理。
- `Match` 指向 `Matcher` 内部的缓冲区，下一次调用后失效。
- `Matcher.Options.step_limit`（默认 1000 万）限制每次搜索的 VM 步数，超出时返回 `error.MatchLimitExceeded`；`stack_limit` 限制回溯栈的条目数（约 32 字节一条），超出时返回 `error.StackLimitExceeded`。
- 编译失败返回 `error.InvalidPattern`，`Diagnostics` 中给出字节偏移和原因（Python 方言沿用 `sre_parse` 的措辞，PCRE2 方言沿用 PCRE2 的）。

## 引擎

`Regex.Options.engine` 选择执行搜索的匹配器，两种方言都适用，结果相同：

- `.backtrack`（默认）：回溯 VM，支持全部语法。最坏情况下耗时随输入指数增长，由 `step_limit` 截断。
- `.pike`：Pike VM，耗时与输入长度成线性（乘以模式大小）。支持字面量、字符类、`.`、分支、贪婪与懒惰量词（含计数）、捕获组与非捕获组、全部零宽断言（`^ $ \A \Z \z \b \B \G`）。
  - 模式含有以下任一构造时，编译返回 `error.UnsupportedByEngine`，`Diagnostics` 说明原因：反向引用、前后顾、原子组、占有量词、递归与调用、条件组、回溯动词、`\K`、`\R`、`\X`，或体可能匹配空串的重复（如 `(a?)*`；`(a?){3}` 这类定次重复可以）。
  - 部分匹配仍由回溯 VM 执行。
- `.auto`：先用回溯 VM。某次搜索超出 `step_limit` 或 `stack_limit` 时，若 Pike VM 支持该模式，就用它重做这次搜索，不再报错。模式自己用 `(*LIMIT_MATCH=n)` 设了上限时不回退，以保持与 PCRE2 一致。

`Regex.patternInfo().pike_supported` 表示模式是否在 Pike VM 的支持范围内。

Pike VM 通常比回溯 VM 慢 2–7 倍（见 [docs/perf-design.md](docs/perf-design.md) 第 5 节），所以它不是默认引擎。处理不可信的模式或输入时，用 `.auto` 或 `.pike`。

## 实现

| 文件 | 内容 |
| --- | --- |
| `src/root.zig` | 对外 API：`Regex`、`Matcher`、`Match`、`Iterator`；搜索循环与起点优化（两种引擎共用） |
| `src/parse.zig` | Python 方言：模式 → AST，报错条件参照 `sre_parse` |
| `src/pcre2_parse.zig` | PCRE2 方言：模式 → AST，照 `parse_regex()`、`check_escape()` 与后顾长度检查 |
| `src/ast.zig` | 两种方言共用的语法树 |
| `src/simplify.zig` | 编译前改写 AST：单码点分支合并成字符类 |
| `src/compile.zig` | AST → 字节码；计数量词用计数循环，单字符重复用 `star` 指令；自动占有化（可越过组结尾、可选项与分支） |
| `src/vm.zig` | 回溯 VM：显式栈加撤销日志；调用帧、回溯动词的信号、部分匹配 |
| `src/pike.zig` | Pike VM：AST → 指令（计数重复展开），按优先级同步推进全部线程 |
| `src/study.zig` | 编译期分析：锚定、行首、首字节集合、必需字节、最短长度 |
| `src/substitute.zig` | 替换模板 |
| `src/CharClass.zig` | 字符类：区间表、属性测试、ASCII 位图 |
| `src/unicode.zig` | 字符属性与大小写折叠查询 |
| `src/unicode_tables.zig` | 由 `tools/gen_unicode_tables.py` 从 Python 3.14（Unicode 16.0）生成 |
| `src/ucd_tables.zig` | 由 `tools/gen_ucd_tables.py` 从 PCRE2 的 `maint/Unicode.tables`（Unicode 17.0）生成 |

## 测试

```sh
zig build test                                   # 单元测试
zig build probe -Doptimize=ReleaseSafe           # Python 方言差分测试用的探针程序
uv run --no-project --python 3.14 python tools/regex_diff.py -n 40000 --seed 1
uv run --no-project --python 3.14 python tools/regex_diff.py -n 40000 --seed 1 --engine pike

# PCRE2 方言：把 C 版 PCRE2 编进测试工具，需要一份 PCRE2 源码检出
P=-Dpcre2-src=/path/to/pcre2
zig build pcre2-diff $P -Doptimize=ReleaseSafe -- -n 40000 --seed 1   # 随机差分
zig build pcre2-testdata $P -Doptimize=ReleaseSafe                    # 上游 testdata
# 以上两项加 `-- --engine pike`：Pike VM 支持的模式改用它，其余照常
zig build pcre2-ref $P -- i 'a(b)c' xABCx                            # 查询 C 版的行为
zig build pcre2-bench $P -Doptimize=ReleaseFast                       # 与 C 版解释器计时对比
```

- `tools/regex_diff.py` 随机生成覆盖 Python 方言语法的模式、输入和替换模板，逐个比较 Python `re` 与本库给出的每个匹配、每个组的位置以及 `re.sub` 的结果。Python 侧每个用例限时 2 秒，因为它没有步数上限。
- `pcre2-diff` 在同一进程里对比本库与 libpcre2：是否报错、组数、`/g` 扫描的每个匹配和组、`(*MARK)`、部分匹配、`pcre2_substitute` 的结果。
- 三个差分工具都可以加 `--engine pike`：支持的模式用 Pike VM 比较，并报告这样的用例数。`pcre2-diff` 还接受 `--engine auto`。
- `pcre2-testdata` 读取上游 `testdata/testinputN`，用 C 版 PCRE2 现场算出期望结果再比较，不依赖 `testoutputN`。用到本库没有的 pcre2test 修饰符、不支持的功能或非 UTF-8 输入的用例会被跳过，汇总时按原因计数。

已知差异（Python 方言）：
- 嵌套量词，如 `((.*)+x)*`：Python 对单字符重复有快速路径，本库可能先触及步数上限；
- 后顾中引用此前的组：Python 允许，本库报错。

已知差异（PCRE2 方言）：
- 含 `(*COMMIT)` `(*PRUNE)` `(*SKIP)` `(*THEN)` 的模式总是从每个起点尝试，相当于 PCRE2 的 `PCRE2_NO_START_OPTIMIZE`。PCRE2 默认的起点优化会改变这些动词的结果，例如 `(*COMMIT)abc` 匹配 `xyzabc`，本库不匹配。部分匹配同样按不做起点优化处理。
- 只含 `(*MARK)` 的模式在无匹配时由 `lastMark()` 报告的名字，可能因起点优化不同而与 PCRE2 不同（PCRE2 文档也建议此时关闭优化）。
- 非法 UTF-8 的主题按字节匹配，PCRE2 会报 UTF-8 错误。
- 递归死循环检测（`error.RecursionLoop`）对“已检查到的最远位置”的追踪是近似的。
- PCRE2 10.50 自身的问题，本库不照搬：
  - 自动占有化把 `.` 与 `\R` 视为不相交，`.{2,}\R` 匹配不到 `"ab\r"`（关闭自动占有化后可以）；
  - 量词为 `{0}` 的组若第二个分支以 `\A` 开头，整个模式被当作锚定的，如 `(?:c|\A){0}x` 匹配不到 `abcx`。