正则表达式规范似乎表现出指数级内存消耗

Question

此示例代码在较长输入的情况下可能会 OOM，并且似乎会逐渐指数级变慢。如果不是 bug，那么它对于测试套件来说是一个有用的例子。

`
(s/def ::thing
(s/+ (s/alt :x (s/+ (set (range 70))))))

(time (s/conform ::thing (range 10))) ;; 30ms
(time (s/conform ::thing (range 15))) ;; 500ms
(time (s/conform ::thing (range 20))) ;; 24s
`

来自 Clojurians Slack 的用户 @petrus 的抓取，由 Max Penet 进行简化。

Answer 1

评论由：mpenet 发布

该示例可以被简化为

`
(s/def ::thing
(s/+ (s/alt :x (s/+ (set (range 70))))))

(time (s/conform ::thing (range 10))) ;; 30ms
(time (s/conform ::thing (range 15))) ;; 500ms
(time (s/conform ::thing (range 20))) ;; 24s
`

Answer 2

评论由：gshayban 发布

感谢 Max 简化！

Answer 3

参考：https://clojure.atlassian.net/browse/CLJ-2327（由 gshayban 报告）