bug#10651: compiling pattern matching for (or ...) takes forever

[rixed@happyleptic.org]

Not really a bug per se (although the manual states that "When Guile
hangs or takes forever to complete a task, it is a bug."), but the time
complexity behind the compilation of (or ...) patterns in (ice-9 match)
module is so high that anything more than 8 sub-patterns takes forever
for me.  Here is a short demonstration of the problem:

% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b)) 'ab])"
 0.06s user 0.00s system 102% cpu 0.054 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 0.13s user 0.01s system 99% cpu 0.136 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 0.44s user 0.01s system 100% cpu 0.443 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 1.78s user 0.01s system 100% cpu 1.792 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 7.28s user 0.02s system 100% cpu 7.308 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 29.31s user 1.50s system 99% cpu 30.823 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])"
 133.75s user 0.14s system 99% cpu 2:13.94 total
% time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) % ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) 'ab])"
 ?

It's easy to work around by splitting the or in smaller chunks but it
can take some time to understand why the compiler hangs. I believe such
time complexity behavior should be advertised in the manual.