regex spec seems to exhibit exponential memory consumption

Question

This example code will OOM on not very long input, and seems to get exponentially slower until then. If it's not a bug, it's a useful example for the test suite.

`
(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
`

Captured from user @petrus on Clojurians Slack, reduced repro by Max Penet.

Answer 1

Comment made by: mpenet

The example could be reduced to :

`
(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

Comment made by: gshayban

Thanks Max for the simplification!

Answer 3

Reference: https://clojure.atlassian.net/browse/CLJ-2327 (reported by gshayban)