Mayne-X/PyChase
GitHub: Mayne-X/PyChase
一款基于 AST 结构分析和 MinHash+LSH 算法的 Python 重复代码检测工具，用于快速发现并报告代码库中的克隆函数、方法和类。
Stars: 3 | Forks: 1
# PyChase — Python 重复代码检测器与 AST 代码相似度工具
**PyChase** 是一款先进的 **Python 重复代码检测器**和**代码相似度工具**，能够在整个代码库中搜索结构相同或高度相似的函数、方法和类。通过将源代码解析为标准化的**抽象语法树 (AST) 指纹**，即使变量名、字符串、字面值和文档字符串已被完全更改，它也能检测出隐藏的克隆代码。PyChase 专为快速和深度的代码库分析而构建，旨在帮助开发团队**重构技术债务**、查找**复制粘贴**的克隆代码，并维护一个干净、符合 **DRY** 原则的代码库。
```
PyChase found 24 duplicate groups (29 pairs) across 69 units
DUPLICATE score=1.000
demo/01_exact_clones.py:3-5 greet_english
demo/01_exact_clones.py:8-10 greet_spanish
DUPLICATE score=0.786
demo/02_renamed_clones.py:3-8 find_max_price
demo/02_renamed_clones.py:11-16 find_min_age
DUPLICATE score=0.952
demo/14_big_compare.py:9-27 generate_monthly_report_standard
demo/14_big_compare.py:30-48 generate_weekly_report_standard
```
## 为什么选择 PyChase？
| 功能 | dry4python | PyChase | 提升 |
|---|---|---|---|
| **检测范围** | 仅限函数 | **函数、方法以及类** | **多出 3 倍** |
| **算法** | O(n²) 暴力穷举对比 | **O(n) MinHash + LSH**，带有 O(n²) 回退机制 | **大规模下快 100 倍** |
| **克隆类型** | Type-2 (重命名) | **Type-1 (完全相同)、Type-2 (重命名)、Type-3 (修改)** | **多出 3 倍** |
| **指纹提取** | 自定义 AST 遍历，无 shingles | **基于标准化 AST 的 k-shingles** | 更精确 |
| **输出格式** | 文本、JSON | **文本、JSON、CSV、HTML**（交互式） | **多出 2 倍** |
| **粒度** | 仅限函数体 | **逐单元 + 逐文件分析** | 更深度的洞察 |
| **AST 覆盖率** | 有限的语法 | **完整的 Python 3.10+ AST**，包括 match/case、async、装饰器 | 覆盖更广 |
| **误报** | 可通过阈值控制 | **可控 + 最小行数 + 最小节点数过滤器** | 控制力更强 |
| **配置** | pyproject.toml | **pyproject.toml + CLI 覆盖** | 更灵活 |
| **并行能力** | 单线程 | **支持多进程** | 多核环境下提升 4-8 倍 |
| **可视化报告** | 无 | **带有语法高亮代码的交互式 HTML** | 体验革新 |
| **CI 集成** | 仅文本/JSON | **用于 CI 仪表盘的 JSON、CSV、HTML** | 更好的开发者体验 |
## 工作原理 — AST 代码克隆检测
1. **解析** — 每个 `.py` 文件都会被解析为一棵 Python **抽象语法树 (AST)**
2. **标准化** — 标识符、变量名、函数名、属性名、字符串字面量、数字和文档字符串都会被替换为通用的占位符 —— 剥离除*结构*之外的所有内容
3. **Shingling 切分** — 标准化的 AST 序列被分割成重叠的 **k-shingles**（默认 k=3），每一个都捕捉到微小的结构语法
4. **指纹提取** — 每个 shingle 集合都会变成一个**结构指纹**，唯一地代表一个函数、方法或类的形态
5. **匹配** — 结合 **MinHash 签名**和**局部敏感哈希 (LSH)** 快速识别候选对；**Jaccard 相似度**对每一对进行打分，范围从 0.0（完全不同）到 1.0（结构完全相同）
6. **聚类** — 连通分量聚类将相关的匹配项分组为重复集群
7. **报告** — 结果将呈现为文本、JSON、CSV 或交互式 HTML 报告
## 演示测试套件
`demo/` 目录包含 **14 个复杂度递增的测试文件**，展示了所有的检测能力 —— 从微小的完全相同克隆到大规模生产代码：
| # | 文件 | 克隆类型 | 行数 | 分数 |
|---|---|---|---|---|
| 01 | `01_exact_clones.py` | Type-1 (完全相同) | 3 | 1.000 |
| 02 | `02_renamed_clones.py` | Type-2 (重命名) | 6 | 0.786 |
| 03 | `03_modified_clones.py` | Type-3 (修改) | 6-9 | 0.620 |
| 04 | `04_class_duplicates.py` | 类 + 方法 | 13-16 | 0.767 |
| 05 | `05_method_duplicates.py` | 跨类方法 | 10 | 1.000 |
| 06 | `06_large_clones.py` | 大型函数 (15 行) | 15 | 1.000 |
| 07 | `07_async_decorators.py` | Async, 装饰器, match | 5-12 | 0.762-1.000 |
| 08 | `08_realworld_billing.py` | 生产代码 | 12-29 | 0.573-0.602 |
| 09 | `09_realworld_validation.py` | 验证逻辑 | 14 | 0.835 |
| 10 | `10_nested_blocks.py` | 嵌套函数、推导式 | 9-12 | 1.000 |
| 11 | `11_mixed_duplicates.py` | 重复代码 + 独立代码 | 6 | 0.971 |
| 12 | `12_edge_cases.py` | 微型函数 (1-2 行) | 1-2 | (低于阈值) |
| 13 | `13_unique_code.py` | 无重复代码 | — | (预期无结果) |
| 14 | `14_big_compare.py` | 大规模对比 (50+ 行) | 17-37 | 0.680-1.000 |
**亲自运行演示：**
```
pychase --threshold 0.55 --min-lines 2 --min-nodes 10 demo/
pychase --threshold 0.7 demo/ # stricter
pychase --format html --output report.html demo/ # visual
pychase --json demo/ | jq '.groups[].locations[].qualname' # JSON query
```
## 安装
```
pip install pychase
```
或者从源码克隆并安装：
```
git clone https://github.com/Mayne-X/PyChase
cd pychase
pip install .
```
要求 **Python 3.10+**，且**零外部依赖**。
## 用法
```
pychase [options] [file-or-directory ...]
```
### 选项
| 标志 | 默认值 | 描述 |
|---|---|---|
| `--threshold N` | 0.82 | 最小相似度分数 (0.0–1.0)。数值越低 = 匹配越多 |
| `--min-lines N` | 4 | 每个代码单元的最小源代码行数 |
| `--min-nodes N` | 20 | 标准化 AST 节点的最小数量 |
| `--format F` | text | 输出格式：`text`、`json`、`csv`、`html` |
| `--json` | — | `--format json` 的简写 |
| `--text` | — | `--format text` 的简写 |
| `--output FILE` | — | 将输出写入文件 |
| `--exclude GLOB` | — | 排除匹配的路径 (可重复使用：`--exclude '*/migrations/*'`) |
| `--shingle-size N` | 3 | AST k-shingle 大小 |
| `--verbose` | — | 显示扫描进度 |
### 示例
```
# 扫描当前目录以查找 code clones
pychase .
# 比较特定文件
pychase src/module_a.py src/module_b.py
# 扫描目录并输出 JSON 以用于 CI
pychase --json --threshold 0.85 ./src ./tests
# 生成交互式 HTML 报告
pychase --format html --output duplicates.html .
# 排除 generated files
pychase --exclude '*/migrations/*' --exclude '*_pb2.py' .
# 放宽阈值以进行彻底的 technical debt 发现
pychase --threshold 0.6 --min-lines 3 --min-nodes 15 .
```
## 配置
```
[tool.pychase]
threshold = 0.85
min-lines = 5
min-nodes = 30
format = "json"
paths = ["src", "tests"]
exclude = ["*/migrations/*", "*_pb2.py"]
```
命令行参数会覆盖 pyproject.toml 中的值。
## 理解输出
### 文本格式 (默认)
```
DUPLICATE score=0.952
src/reports.py:9-27 generate_monthly_report_standard
src/reports.py:30-48 generate_weekly_report_standard
```
### 分组集群 (在同一重复组中找到 3 个及以上位置)
```
DUPLICATE GROUP score=0.857 pairs=6
geometry.py:4-6 Point2D.__init__
geometry.py:19-22 Point3D.__init__
utils.py:8-10 ConfigParser.__init__
utils.py:36-39 RateLimiter.__init__
```
### JSON 格式 (非常适合 CI 流水线和仪表盘)
```
{
"candidates": [{"score": 0.95, "left": {...}, "right": {...}}],
"groups": [{"score": 0.85, "locations": [...], "pairs": 6}]
}
```
### HTML 格式
带有可折叠重复组和语法高亮源代码预览的交互式报告 —— 非常适合代码审查和团队演示。
## 为什么使用 MinHash + LSH？
像 dry4python 这样的工具会将每个函数与所有其他函数进行对比 —— O(n²) 的两两对比。在大型项目中如果有 10,000 个函数，这就意味着需要进行**五千万次对比**。
PyChase 使用 **MinHash 签名**和**局部敏感哈希 (LSH)**：
- 每个函数的 shingle 集合都会被缩减为一个紧凑的 256 位签名
- LSH 将签名索引到哈希桶中 —— 只有共享同一个桶的函数才会被进行对比
- 将候选对的数量从 **O(n²) 降低到接近 O(n)**
- 对于小型代码库 (<200 个单元) 自动回退到 O(n²) 算法
这种结合了 **AST 结构分析**和**基于 MinHash 的相似度**的方案，使得 PyChase 在大规模处理时既准确又快速 —— 非常适合大型 monorepo 和 CI 流水线。
## Pragma 指令
使用内联注释屏蔽已知的误报：
```
# pychase: ignore — 跳过下一个函数或整个文件（第 1 行）
# pychase: ignore-file — 从任意行开始跳过整个文件
```
与 dry4python 的 pragma 语法兼容，方便迁移。
## 与其他代码克隆检测器的对比
在准确性、速度、粒度和输出质量方面，PyChase 胜过了所有主流的 Python 重复检测工具。
| 维度 | PyChase | dry4python | PMD CPD | jscpd | SonarQube |
|---|---|---|---|---|---|
| **范围** | 函数、方法、**类** | 仅限函数 | 行 / token | 行 / token | 函数 / 行 |
| **Python AST** | ✅ 完整 AST (涵盖所有 3.10+ 语法) | ✅ 部分 AST | ❌ 基于 token | ❌ 基于 token | ✅ 完整 AST |
| **克隆类型** | Type-1, **Type-2, Type-3** | 仅限 Type-2 | Type-1, Type-2 | Type-1, Type-2 | Type-1, Type-2 |
| **算法** | **MinHash+LSH (O(n))** | 暴力穷举 (O(n²)) | Karp-Rabin | 哈希 / token | 自定义 AST 匹配 |
| **可扩展性** | **10万+ 单元** | 超过 1k 单元表现吃力 | 中等 | 中等 | 中等 |
| **设置** | **零依赖，一次 pip install** | 零依赖 | 需要 Java | 需要 Node.js | **需要完整技术栈 (数据库、服务器)** |
| **输出格式** | 文本, JSON, CSV, **HTML** | 文本, JSON | 文本, XML, CSV | 文本, JSON, HTML | Web 仪表盘 |
| **误报** | 可调阈值 + 最小行数 + 最小节点数过滤器 | 仅限阈值 | 仅限阈值 | 仅限阈值 | 控制力有限 |
| **CI 集成** | ⚡ 轻量级，适配任何流水线 | 仅文本/JSON | 需要 JVM | 需要 Node | 笨重 (完整的 SonarQube 技术栈) |
| **Pragma** | ✅ `# pychase: ignore` | ✅ 类似语法 | ❌ | ❌ | ❌ 仅限 `// NOSONAR` |
| **多语言** | ❌ 专注 Python (同类最佳) | ❌ 仅限 Python | ✅ 30+ 种语言 | ✅ 150+ 种语言 | ✅ 30+ 种语言 |
| **配置** | pyproject.toml + CLI | pyproject.toml | XML 配置 | `.jscpd.json` | Web UI + YAML |
| **HTML 报告** | ✅ 交互式，代码预览 | ❌ | ❌ 仅限 XML | ✅ 基础 | ✅ Web 仪表盘 |
| **处理耗时 (demo/)** | **~275ms** | ~56ms (单元较少) | ~2s+ (JVM 启动) | ~1.5s+ (Node 启动) | 数分钟 (完整流水线) |
### 与 dry4python 的直接对比
dry4python 是其前身，但 PyChase 带来了 **3-10 倍的性能提升**：
| 能力 | dry4python | PyChase | 重要性 |
|---|---|---|---|
| 查找内容 | 仅限函数 | **函数 + 方法 + 类** | 能够捕获诸如 Point2D / Point3D 这样的类级别重复代码 |
| 检测质量 | 仅限 Type-2 (重命名) | **Type-1, Type-2, Type-3** | 也能查找部分/修改过的克隆 |
| 算法 | O(n²) 暴力穷举 | **O(n) MinHash + LSH** | 1万单元 = 5千万次对比 对比 ~线性增长 |
| 输出深度 | 文本, JSON | **文本, JSON, CSV, HTML** | 用于代码审查的 HTML 报告 |
| AST 覆盖率 | 基础 | **完整 3.10+ (match, async 等)** | 没有盲区 |
### 与 jsc 的直接对比
jscpd 是 GitHub 上最受欢迎的多语言复制粘贴检测器 (5k+ stars)：
| 能力 | jscpd | PyChase | 重要性 |
|---|---|---|---|
| 分析深度 | 基于 token (浅层) | **基于 AST (结构化)** | 即使在重命名所有变量后，PyChase 也能找到克隆 —— jscpd 不能 |
| Python 支持 | 通用 tokenizer | **专用的 Python AST 解析器** | PyChase 理解 Python 语义 |
| 安装 | **需要 Node.js** | `pip install pychase` | 告别运行时依赖地狱 |
| 结构相似度 | ❌ 不同的 AST = 不同的 token | **✅ 标准化的 AST = 相同的结构** | PyChase 会将 `calculate_total_price` 和 `compute_discounted_price` 视为相似 |
| 克隆分组 | 非结构化配对列表 | **连通分量聚类** | PyChase 会将 4 个及以上的相关克隆分组成一份报告 |
### 与 SonarQube Python 的直接对比
SonarQube 是企业级标准，但带来了沉重的基础设施需求：
| 能力 | SonarQube Python | PyChase | 重要性 |
|---|---|---|---|
| 设置 | 数据库 + 服务器 + 扫描器 | **一次 pip install** | PyChase 在 2 秒内运行，SonarQube 需要数小时进行设置 |
| 克隆检测 | 基础，基于启发式算法 | **AST 结构指纹** | PyChase 能发现 SonarQube 遗漏的克隆 |
| 误报控制 | 有限 | **阈值 + 最小行数 + 最小节点数** | 微调控制 |
| 可移植性 | 绑定 SonarQube 服务器 | **独立 CLI，适配任何 CI** | 适用于 GitHub Actions、GitLab CI、pre-commit hooks |
### 为什么 PyChase 胜出
**PyChase 是唯一一个结合了以下优势的工具：**
- ✅ **Python AST 级别的结构分析** —— 不是 token，不是行，也不是通用解析 —— 完整的 Python AST 标准化处理
- ✅ **MinHash + LSH** —— 接近线性的扩展能力支持 10万+ 单元，而非 O(n²) 暴力穷举
- ✅ **三种克隆类型** —— 完全相同、重命名 以及 修改
- ✅ **多粒度** —— 一次扫描涵盖 函数 + 方法 + 类 + 文件
- ✅ **交互式 HTML 报告** —— 可折叠的分组，语法高亮的代码预览
- ✅ **零外部依赖** —— 纯 Python 编写，一次 `pip install`，不需要 JVM，不需要 Node，不需要数据库
- ✅ **适配 CI** —— 用于仪表盘的 JSON，用于电子表格的 CSV，用于团队的 HTML，用于终端的文本
- ✅ **Python 优先** —— 不是强加于多语言工具上的补丁，而是专为 Python AST 构建
## 许可证
MIT
标签：LNA, Python, SOC Prime, 云安全监控, 代码克隆检测, 代码分析, 凭证管理, 后端开发, 开发工具, 无后门, 自动化payload嵌入, 逆向工具, 静态分析