\title{内存级源代码大小写折叠技术}
\author{杨子凡}
\date{Aug 04, 2026}
\maketitle
在一次对开源编译器前端的代码审计中，开发者发现三处表面上完全不同的 Bug 其实指向同一份源码，只是因为大小写不一致而被误判为三个独立问题。问题的根源在于，Unicode 源文件在不同编码或平台上可能出现「视觉等价但二进制不等」的情况。文章将聚焦于「在内存里做大小写折叠」，不涉及磁盘或网络，只面向编译器、编辑器、IDE 及静态分析工具的开发者。\par
\chapter{背景与术语}
大小写折叠与规范化是两个正交的概念。规范化处理的是视觉或语义等价的字符序列，例如将「é」拆成「e」+ 组合重音符；而大小写折叠则仅关注字母形态的转换，把「A」映射为「a」。Unicode 标准在三个数据文件中定义了相关属性：Simple\_{}Lowercase\_{}Mapping 给出最简单的单码位映射，Special\_{}Casing.txt 处理 Turkish 的 I/ı、Lithuanian 的 i/J 等特殊场景，Case\_{}Folding.txt 则提供完整的折叠表。在内存层面，零拷贝、原地改写与不可变字符串的取舍直接决定了接口设计；工程上还要决定：折叠仅作用于标识符，还是同时处理字符串字面量与注释。\par
\chapter{Unicode 大小写折叠算法速览}
简单折叠与完全折叠的区别在于是否展开多码位。简单折叠保证输出长度不变，完全折叠允许把一个码位展开为多个，例如 U+0130「İ」会变成「i」+ 组合点。Turkish 的「I」在小写时必须映射为「ı」而非 ASCII「i」，German 的「ß」则折叠为「ss」。在性能上，ASCII 区可直接用 256 字节查表，BMP 之外则需要 HashMap 或两级表。公式上，映射过程可表示为 ( c' = \textbackslash{}text\{{}casefold\}{}(c) )，其中 ( c, c' ) 均为 Unicode 码位。\par
\chapter{内存数据结构设计}
为了达到单码位 O(1) 或 O(log n) 的折叠速度，可选方案包括 256 字节 ASCII 表、两级表（块表 + 数据表）、Robin-Hood Hash，以及 SSE4.2/AVX2/NEON 的 SIMD 快速路径。Rust 的 \&{}str 是不可变 UTF-8 切片，若要原地改写，需先转为 Vec<u8>；Go 里 []byte 可变而 string 不可变，二者互转会触发拷贝。设计时需权衡：零堆分配能降低 GC 压力，但 SIMD 寄存器对齐和长度扩张场景又需要额外的缓冲策略。\par
\chapter{实现路线图（以 Rust 为例）}
原型阶段直接调用标准库 \texttt{to\_{}lowercase()} 作为基线。零堆分配阶段先按最坏情况预分配 3×len 的 Vec<u8>，然后逐码位写入；若映射后长度不变，可直接原地改写，避免额外分配。SIMD 特化阶段将 ASCII 块交给 SIMD 指令，剩余 BMP 外码位仍用标量循环。并行分片阶段借助 Rayon，按 chunk 边界对齐到码点，避免跨线程的码位截断。零拷贝视图阶段返回 Cow<'\_{}, str>，仅在真正发生变化时拥有堆内存。单元测试需覆盖 ASCII、Latin-1、Emoji、IVS 及未分配码位，确保边界条件不崩溃。\par
下面这段 Rust 代码演示了零堆分配的折叠流程：\par
\begin{lstlisting}[language=rust]
fn fold_lower(s: &str) -> Vec<u8> {
    // 预分配 3 倍长度，足以容纳多码位展开
    let mut out = Vec::with_capacity(s.len() * 3);
    for ch in s.chars() {
        // 利用标准库 CaseMapping 迭代器
        for lc in ch.to_lowercase() {
            // 每个小写字符都写入输出缓冲
            let mut buf = [0; 4];
            let n = lc.encode_utf8(&mut buf).len();
            out.extend_from_slice(&buf[..n]);
        }
    }
    out
}
\end{lstlisting}
这段代码首先按最坏情况申请三倍容量，随后对输入字符串的每个字符调用 \texttt{to\_{}lowercase()}，该方法返回一个迭代器，可能产出一个或多个小写字符；每个小写字符再编码为 UTF-8 并写入输出缓冲，从而完成零堆分配的折叠。\par
\chapter{常见陷阱与对策}
代理对截断是 UTF-16 到 UTF-8 转换时最易忽略的问题：若在码点中间截断，会导致后续解码失败。对已损坏的 UTF-8，lossy 策略能保证工具不断，而 hard-fail 则能及早暴露数据问题。特殊大小写导致的长度变化，如 U+00DF「ß」折叠为「ss」，会让原地改写变得不可能，必须分配新缓冲。标识符做 Hash 时，若在插入 DashMap 前先折叠，可避免重复计算；但若在 Hash 过程中同步折叠，则需保证折叠后的字节序列与原始序列具有相同的哈希种子。IDE 的高亮与重构需要维护「折叠前后偏移映射表」，以便在用户点击时准确定位原始源码位置。\par
\chapter{性能评测与 A/B}
测试语料包括 Linux 6.4 全树 C 代码、Chromium 第三方的 JavaScript，以及 Rust 标准库源码。指标涵盖吞吐量、p99 延迟与内存峰值。实测结果显示，SIMD 版比基线快 4 – 6 倍，且内存零增长。\par
\chapter{工程集成示例}
在 rust-analyzer 中，可将折叠后的标识符作为键插入 DashMap<FoldedKey, Span>，从而实现大小写不敏感的符号索引。clangd 通过 FoldingService 加速符号索引构建，tree-sitter 则新增 case-insensitive 查询谓词。下面这段代码展示了如何把折叠后的键插入 DashMap：\par
\begin{lstlisting}[language=rust]
use dashmap::DashMap;
let map: DashMap<FoldedKey, Span> = DashMap::new();
// folded 是前面 fold_lower 返回的 Vec<u8>
let key = FoldedKey::from_bytes(&folded);
map.insert(key, span);
\end{lstlisting}
这段代码首先创建线程安全的 DashMap，随后把折叠后的字节序列包装成 FoldedKey 类型作为键，与源码位置 Span 一起插入；由于键已折叠，查询时无论用户输入大小写均可命中。\par
\chapter{扩展话题}
大小写折叠与 NFC/NFD 规范化正交，可先折叠再规范化，也可反之。在安全领域，稳定的、不依赖区域设置的折叠能防止 SSRF 与原型污染攻击。未来可借助 const generics 在编译期生成 FoldingTable，进一步降低运行时开销。\par
内存级大小写折叠是「短平快」的质量杠杆。推荐 MVP 方案是先实现 ASCII 快速路径加 Unicode 查表，随后引入 SIMD 与并行，最后与规范化流水线串联。\par
