CodeShark37/Xgen
GitHub: CodeShark37/Xgen
Xgen 是一个 C 语言库，根据语义别名组、依赖关系、互斥规则与权重约束，穷举生成所有合法的命令行参数组合。
Stars: 1 | Forks: 0
Português | [English](README_en.md)
[](#)
[](#)
[](#)
[](#)
## 目录
- 什么是 Xgen？
- 功能
- 安装说明
- 快速开始
- 使用指南
- 数据模型
- Constraints: 依赖与互斥
- 权重过滤
- 辅助宏
- 实践示例
- 参考 API
- 故障排除
- 贡献
## 什么是 Xgen？
**Xgen** 是一个 C 语言库，它根据语义等效的别名组，穷举且不重复地生成所有有效的命令行参数组合——同时遵守用户定义的依赖、互斥和权重限制。
每当需要系统地为 CLI 生成测试用例时，它都非常有用：定向 fuzzing、参数解析器的回归测试，或者仅仅是探索具有许多相互依赖 flags 的程序的有效组合空间（例如 `gcc`）。
**兼容性：**
- **操作系统：** Linux, Windows
- **架构：** x86, x86_64, ARM, AArch64
- **标准：** C11+
## 功能
| 类别 | 功能 | 详情 | 状态 |
|-----------|---------|--------|-----------|
| **Core** | 组合生成 | 状态机探索 k-组合、排列和别名 | 完整 |
| **Constraints** | 依赖 | AND (`DEP`) 和 OR (`DEP_OR`) | 完整 |
| **Constraints** | 互斥 | 成对 (`EXCL`) 以及针对多个目标的扩展成对 (`EXCL_OR`) | 完整 |
| **过滤** | 累积权重 | `max_weight` 根据成本/复杂度过滤组合 | 完整 |
| **性能** | Memoização | 依赖/互斥的验证在组级别进行，而不是针对每个别名/排列重复进行 | 完整 |
| **模式** | 生成 | `GEN_MODE_LEXICAL` 和 `GEN_MODE_COMBINATORIAL`（包含排列） | 完整 |
| **控制** | 输出限制 | `limit` 在 N 个组合后截断生成 | 完整 |
| **健壮性** | 配置验证 | `gen_create()` 拒绝不可能的配置（无法解决的循环、k > group_count 等） | 完整 |
| **性能** | 零依赖 | 仅依赖 C 标准库 (stdlib) | 完整 |
| **测试** | 边缘情况 + fuzzing 测试套件 | 循环、自引用、依赖与互斥冲突、负权重 | 辅助工具
### 探索的组合空间
```
# 生成器在四个轴上迭代：
1. Valores de k (min_args .. max_args) — quantos grupos por combinação
2. k-combinações de grupos — quais grupos participam
3. Aliases dentro de cada grupo seleccionado — qual forma do argumento usar
4. Permutações da ordem dos grupos (se activado) — em que ordem os argumentos aparecem
# 每个候选组合仅在满足以下条件时才会输出：
- Todas as Dependency (from requer pelo menos um de to[])
- Todas as Exclusion (a não pode coexistir com NENHUM elemento de b[])
- max_weight (soma dos pesos dos grupos seleccionados)
```
## 安装说明
### 前置条件
- C11+ 编译器 (gcc, clang)
### 快速安装
```
# Clone 该 repository
git clone https://github.com/CodeShark37/xgen.git
# 进入该 directory
cd xgen
# 编译为 static library，或者直接将 xgen.c/xgen.h 包含到您的 project 中
gcc -c -O2 xgen.c -o xgen.o
```
### 基本用法
```
#include "xgen.h"
int main(void) {
const char *help[] = { "--help", "-h" };
ArgGroup groups[] = { { help, 2, 0 } };
GenConfig cfg = {0};
cfg.groups = groups;
cfg.group_count = 1;
cfg.min_args = 1;
cfg.max_args = 1;
Generator *gen = gen_create(&cfg);
if (!gen) return 1;
const char **args;
size_t count;
while (gen_next(gen, &args, &count)) {
for (size_t i = 0; i < count; i++)
printf("%s ", args[i]);
printf("\n");
}
gen_free(gen);
return 0;
}
```
## 使用指南
### 生成器的生命周期
| 步骤 | 函数 | 描述 |
|-------|--------|-----------|
| 1. 创建 | `gen_create(&cfg)` | 验证配置并返回 `Generator*`，如果不存在有效组合则返回 `NULL` |
| 2. 迭代 | `gen_next(gen, &args, &count)` | 返回当前组合并前进；结束时返回 `false` |
| 3. 查询 | `gen_emitted(gen)` / `gen_done(gen)` | 迭代的进度和状态 |
| 4. 释放 | `gen_free(gen)` | 释放所有内部内存 |
### `GenConfig` 选项
| 字段 | 类型 | 描述 |
|-------|------|-----------|
| `groups` / `group_count` | `ArgGroup*` / `size_t` | 可用的参数组 |
| `min_args` / `max_args` | `size_t` | 组合的大小 k 范围 |
| `deps` / `dep_count` | `Dependency*` / `size_t` | 依赖规则（可选） |
| `excls` / `excl_count` | `Exclusion*` / `size_t` | 互斥规则（可选） |
| `max_weight` | `int` | 最大累积权重（`0` = 无限制） |
| `limit` | `size_t` | 最多输出的组合数量（`0` = 无限制） |
| `mode` | `GenMode` | `GEN_MODE_LEXICAL` 或 `GEN_MODE_COMBINATORIAL` |
## 数据模型
### ArgGroup — 一组等效的别名
```
const char *verbose[] = { "--verbose", "-v", "--debug" };
ArgGroup g = { verbose, 3, /* weight */ 1 };
```
当一个组被选中用于组合时，它的别名中确切地只有一个会出现在输出中——Xgen 会针对每个别名生成一个变体。
### 组索引
所有依赖和互斥规则都通过它们在 `groups[]` 数组中的**索引**来引用组。使用本地的 `enum` 来命名这些索引会使规则更加易读：
```
enum { G_INPUT, G_OUTPUT, G_VERBOSE };
```
## Constraints: 依赖与互斥
### 依赖 (`Dependency`)
一个依赖表明：*“如果选中了 `from`，那么 `to[]` 中的至少一个也必须被选中”*。
| 形式 | 语义 | 宏 |
|-------|-----------|-------|
| `to_count == 1` | 经典 AND —— `from` 需要 `to` | `DEP(from, to)` |
| `to_count > 1` | OR —— `from` 需要 `{...}` 中的至少一个 | `DEP_OR(from, ...)` |
```
enum { G_OUTPUT, G_FORMAT };
Dependency deps[] = {
DEP(G_OUTPUT, G_FORMAT), /* --output requer --format */
};
```
### 互斥 (`Exclusion`)
互斥表明：*“`a` 不能与 `b[]` 中的**任何**元素共存”*——只要 `a` 旁边存在 `b[]` 中的一个元素，该组合即为无效。
| 形式 | 语义 | 宏 |
|-------|-----------|-------|
| `b_count == 1` | 经典成对——`a` 和 `b` 相互排斥 | `EXCL(a, b)` |
| `b_count > 1` | 扩展成对——`a` 与 `{...}` 中的**任何一个**单独在一起均无效；等同于在单个规则中声明 `EXCL(a, b0)`、`EXCL(a, b1)`、... | `EXCL_OR(a, ...)` |
```
enum { G_QUIET, G_VERBOSE };
Exclusion excls[] = {
EXCL(G_QUIET, G_VERBOSE), /* --quiet e --verbose são mutuamente exclusivos */
};
```
## 权重过滤
每个 `ArgGroup` 都有一个 `weight`（可以为负）。通过在 `GenConfig` 中设置 `max_weight`，将仅输出权重总和不超过该限制的组合。`max_weight == 0` 会禁用此检查。
```
ArgGroup groups[] = {
{ light, 2, 1 }, /* peso 1 */
{ heavy, 2, 5 }, /* peso 5 */
};
cfg.max_weight = 4; /* {light} passa; {heavy} e {light,heavy} são filtrados */
```
## 辅助宏
| 宏 | 用法 |
|-------|-----|
| `DEP(from, to)` | 简单的 AND 依赖 |
| `DEP_OR(from, ...)` | OR 依赖（可变参数） |
| `EXCL(a, b)` | 成对互斥 |
| `EXCL_OR(a, ...)` | 针对多个目标的扩展成对互斥（可变参数） |
| `COUNT_ARGS(...)` | 被 `DEP_OR`/`EXCL_OR` 用于计算可变参数数量的内部辅助工具 |
## 实践示例
### 依赖链
```
enum { G_FORMAT, G_OUTPUT, G_COMPRESS };
Dependency deps[] = {
DEP(G_OUTPUT, G_FORMAT), /* output requer format */
DEP(G_COMPRESS, G_OUTPUT), /* compress requer output */
};
/* Válido: [--format], [--format --output], [--format --output --compress]
Inválido: [--output] (falta format), [--compress --output] (falta format) */
```
### 针对多个目标的扩展成对互斥
```
enum { G_SAFE, G_OPT_SPEED, G_OPT_SIZE, G_PARALLEL };
Exclusion excls[] = {
/* --safe-mode não pode coexistir com --optimize-speed, nem com
--optimize-size, nem com -Instalação cada par é excluído
individualmente (não é preciso os três estarem presentes juntos) */
EXCL_OR(G_SAFE, G_OPT_SPEED, G_OPT_SIZE, G_PARALLEL),
};
```
### 真实场景：编译器 flags（GCC 风格）
一个完整的用例——大约 20 个参数组、21 个依赖关系以及仅 3 条扩展成对互斥规则（而不是 25 条单独的 `EXCL` 规则）——已在 `examples.c` 中实现，包括：
```
/* Info é sempre standalone: exclui, um a um, TODOS os outros grupos
numa única regra (nenhum deles pode coexistir com Info) */
EXCL_OR(G_INFO, G_INPUT, G_MODE, G_OUTPUT, G_STD, G_OPT, G_DEBUG,
G_WARN, G_WERROR, G_DEFINE, G_INCLUDE, G_ARCH, G_SANITIZE,
G_LTO, G_PIC, G_SHARED, G_STATIC, G_LIBPATH, G_LIBLINK, G_STACK);
```
请查阅 `examples.c` 获取从最基础用法到 GCC9 模型的七个完整示例；查阅 `tests.c` 了解边缘情况（循环、自引用、依赖与互斥的冲突、负权重）；查阅 `fuzz.c` 获取用于随机压力测试的驱动程序。
## 参考 API
| 函数 | 描述 |
|--------|-----------|
| `Generator *gen_create(const GenConfig *config)` | 创建并验证一个新的生成器；如果配置无法实现则返回 `NULL` |
| `bool gen_next(Generator *gen, const char ***out_args, size_t *out_count)` | 返回当前组合并推进状态 |
| `void gen_free(Generator *gen)` | 释放与生成器关联的所有内存 |
| `size_t gen_emitted(const Generator *gen)` | 已输出的组合数量 |
| `bool gen_done(const Generator *gen)` | 迭代是否已结束 |
关于每个 struct、enum 和函数的完整文档（包含独立示例）位于 `xgen.h` 中，使用 Doxygen 编写。
## 故障排除
| 症状 | 可能的原因 |
|---------|-----------------|
| `gen_create()` 返回 `NULL` | 不可能的配置：任何 k 都无法满足的依赖循环、`min_args > max_args`、`max_args > group_count`，或者最小权重已超过 `max_weight` |
| 没有出现预期的组合 | 检查依赖是否不仅仅是*隐式的*——Xgen 不会传递性地闭合依赖关系 |
| 组合过多 / 生成缓慢 | 减小 `max_args`，设置 `limit`，或者使用 `GEN_MODE_LEXICAL` 代替 `GEN_MODE_COMBINATORIAL` 以避免排列 |
| 负权重导致意外结果 | 负权重照常累加；总权重 ≤ `max_weight` 的组合会通过检查，即使它们包含被负权重组抵消的“重型”组 |标签：参数解析, 客户端加密, 测试用例生成, 组合数学