Java Pattern 怎样避免灾难性回溯

Java 正则能匹配，不代表它在所有输入上都能稳定返回。最容易被忽略的情况是：一个量词已经可以吃掉某段字符，外层量词又把同一段字符重复组织起来，后面再接一个最终会失败的条件。此时 Pattern 可能需要不断退回并尝试另一种切分，输入越长，候选状态越多，匹配就可能从“很快失败”变成“长时间没有结果”。

避免 Java Pattern 灾难性回溯的核心，不是把所有量词都改成 possessive，而是先消除可重叠的重复结构；如果业务上确定某段字符一旦匹配就不应交还给后续表达式，再用 possessive quantifier 或 atomic group 固定边界，同时限制外部输入长度。

为什么重叠量词会把回溯放大

Java 官方 API 将 Pattern 描述为传统的 NFA 式匹配器，并且按正则结构提供贪婪、懒惰和 possessive 等量词。普通贪婪量词会先尽量多匹配；当后面的字面量或分支失败时，匹配器可以退回前面的选择，再尝试另一种长度。

单个 a+ 不一定有问题，真正危险的是多个都能匹配 a 的重复结构发生重叠，例如 (a+)+b。输入是一串 a，结尾却没有 b 时，外层和内层都可能提出不同的切分方式。这里的“灾难性”不是说每次都会按同一个复杂度运行，而是说失败路径可能让候选空间迅速膨胀，不能用一次短字符串的感觉推断线上长输入的表现。

排查时先看三个问题：相邻或嵌套的量词是否能消费同一类字符；某个分支失败后，前面的量词是否还有多种切分；输入是否来自用户、网络或可被放大的字段。只要三个问题同时出现，就不应只靠“这条正则平时很快”来判断安全。

普通贪婪量词、possessive 和 atomic group 有什么区别

这三种写法都能表达“至少一个 a”，但它们的搜索边界不同。possessive quantifier 直接附着在量词后面；atomic group 则把一个子表达式包起来。Java Pattern 的语法同时支持这两类构造，选择哪一种取决于你要锁定的是一个量词，还是一整个子表达式。

用代码把危险结构改成受控结构

下面只展示表达式的结构差别，不把示例当成线上性能测试。第一条表达式的两个量词都能消费 a，当后缀失败时会留下更多回退选择；后两条把已经确认的连续 a 视为不可回退的片段。

import java.util.regex.Pattern;

public class RegexBacktrackingDemo {
    public static void main(String[] args) {
        // 风险结构：内外两个量词都可以消费连续的 a，失败时存在重叠切分。
        Pattern risky = Pattern.compile("(a+)+b");

        // possessive 量词：a++ 匹配后不把已消费的 a 交还给后续表达式。
        Pattern possessive = Pattern.compile("a++b");

        // atomic group：把 a+ 作为一个不可拆分的匹配单元。
        Pattern atomic = Pattern.compile("(?>a+)b");

        // 这里只保存结构示例；实际输入应先做长度和来源边界控制。
        System.out.println(risky.pattern());
        System.out.println(possessive.pattern());
        System.out.println(atomic.pattern());
    }
}

重要边界在于：a++b 不是“更快版本的 a+b”，而是不同语义。如果后续的 b 可能需要前面的量词交还一个字符，possessive 写法会直接失败。改写前要先证明字符集合或业务语法已经把两段分开，例如前段只允许数字、后段必须是分隔符，而不是看到量词就机械添加第二个加号。

什么时候该用 atomic group

如果需要锁定的只是一个字符类或简单量词，a++ 更直观；如果片段由多个部分组成，且整体一旦匹配就不应该被拆开重试，可以考虑 (?>...)。例如某个分隔明确的 token 由字母、数字和连字符组成，后面的分支只接受分隔符，那么可以把 token 作为一个原子单元。反过来，如果后续分支合法地依赖 token 内部的不同切分，就不能加原子组。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class TokenPatternDemo {
    public static void main(String[] args) {
        // token 内部由字母、数字和连字符组成，末尾要求一个冒号。
        Pattern token = Pattern.compile("(?>[A-Za-z0-9-]+):");
        Matcher matcher = token.matcher("order-2026:");

        // matches() 只表达完整输入是否符合该结构，不负责设置超时。
        boolean accepted = matcher.matches();
        System.out.println(accepted);
    }
}

这里的原子组只是表达“token 一旦确定就不再拆分”的业务边界。若 token 后面还允许把连字符重新解释成另一种语法，就应拆成更明确的词法规则，或先用普通字符串扫描完成分段，再对小片段使用正则。

四层工程防护要一起做

1. 先改结构。避免重复量词共享同一字符集合；能用明确分隔符表达，就不要用多个 .* 或宽泛字符类互相竞争。
2. 再限输入。对来自 HTTP、消息队列、表单和日志的待匹配文本设置长度上限；长度限制不能修复坏结构，但能降低单次输入放大的范围。
3. 复用 Pattern。Pattern 编译结果是不可变的，可以在配置加载或初始化阶段复用；Matcher 持有匹配状态，不要让多个线程共享同一个 Matcher。
4. 设置外部时间预算。Matcher API 没有按次匹配的 timeout 参数，不能把线程中断当作可靠的正则停止协议。对不可信输入，必要时把匹配放到可隔离的执行单元，并对超时、拒绝和降级单独记录。

如果表达式已经很复杂，最稳妥的方案往往不是继续叠加 lookaround，而是把解析拆成两步：先用普通字符串方法或小正则识别分隔边界，再对边界内的短字段做精确匹配。这样既能减少回溯空间，也更容易为每一段设置独立的输入约束。

常见问题

把所有 + 都改成 ++ 可以吗？

不可以。++ 会禁止回退，可能改变原表达式本来允许的合法匹配。只有在后续表达式不需要前段字符、并且这个边界能由业务语法证明时才适合使用。

设置有限次数就不会回溯膨胀了吗？

有限次数通常能缩小输入和候选空间，但嵌套且重叠的结构仍可能产生许多组合。应优先消除结构重叠，再用上限作为第二道边界。

Pattern 线程安全吗？

官方 API 将 Pattern 描述为不可变对象，可被多个线程共享；Matcher 保存匹配状态，不适合在多个线程之间直接共享。复用 Pattern 时要为每次匹配创建独立 Matcher，或使用线程隔离的状态。

Java Pattern 能直接设置单次匹配超时吗？

标准 Matcher 接口没有按次 timeout 参数。应用需要在正则结构、输入限制和外部执行隔离之间做组合设计，而不是只依赖一个 API 开关。

最后可以用一句话检查这类代码：后面的失败条件出现时，前面的量词是否有很多种方式重新分配已经吃掉的字符？如果答案是“有”，先重写结构；如果答案是“没有”，再考虑是否需要 possessive 或 atomic group 固定边界，并为不可信输入补上长度和时间预算。