Perl 19:一次“跑得慢”不是复杂度证明
(a+)+ 把“每段由几个 a 组成”和“有几段”交给相邻的两个重复决定。长串 a 后再接一个不匹配的 X,正则不能成功,却有多种切分路线。若把 n 个 a 的 n−1 个空隙分别选为“分段”或“不分段”,数学上存在 2^(n−1) 种正整数分段法;这解释了表达式为何含有组合歧义,不等于证明当前 Perl 引擎真的逐一遍历了全部分段。官方 perlre 的 Backtracking/Atomic Grouping 一节直接讨论类似的 (.+)+ 无匹配模式及原子分组的取舍。
实验仅跑固定长度 6、8、10,再追加 X;命令 perl examples/perl-language/experiments/16-20-patterns.pl 19 的 STDOUT 是 size=6:partitions=32:rejected=1、size=8:partitions=128:rejected=1、size=10:partitions=512:rejected=1,STDERR 空、退出码 0。输出中的 partitions 是上述组合式的计算值,不是引擎运行时间、匹配尝试次数或经过剖析器读出的计数。对照的 \Aa+\z 也拒绝这些带 X 的坏样本。实验不给不可信输入开放模式或任意长度,也没有用某一次秒数声称测出渐进复杂度。
这个坏样本提醒查询模块:对用户字面目标优先直接比较或引用转义,不把输入原样编译成正则。未来真要接受模式,至少需要长度、语法、时间与隔离执行的独立约束;这里只提供有限反例,不能据此宣布面向敌意输入的安全方案已验收。补充课程测试没有把坏样本扩大成性能基准,而是把结论固定为“有限反例”。course-semantics.pl regex 只验证动态点号被误解释和字面化后恢复;原 16-20-patterns.pl 19 只输出 6、8、10 三个规模的组合数。二者合在一起说明设计方向:能用字面包含就不用运行时正则,必须用正则时再给语法、长度、时间和隔离边界。它们仍不是峰值内存、耗时曲线或引擎回溯步数证明。
本次复跑另存一份原始耗时口径:course-semantics.pl backtracking 对 6、8、10 三个规模打印 elapsed_us,证据文件保存完整 stdout。测试只断言字段存在且样本被拒绝,不断言微秒数大小;微秒数受机器、编译选项、系统负载和正则优化影响,只能作为这次运行的原始记录。课程结论仍限于“规模、组合数、拒绝结果和本次耗时已记录”,不把它升级成所有平台或所有输入长度的性能保证。
[PATTERN] 安全结论要和测量口径同宽。partitions=512 是组合式计算,不是 profiler 计数;一次正则返回快,只说明该样本快。课程断言保留小规模正反例,是为了防止误用裸动态模式,不是为了宣布 Perl 5.38.2 的正则引擎已经在所有敌意输入上通过性能验收。
练习:把 X 去掉,为何不能用“匹配很快”反证失败路径风险?能很快找到成功路径,不代表所有失败输入都没有大量候选切分。来源与金标见 examples/perl-language/evidence/15-20.md 和校验过的 Perl 5.38.2 pod/perlre.pod(Backtracking、Atomic Grouping)。









