Original bug ID: 4011
Reporter: @dra27
Status: closed (set by @damiendoligez on 2006-08-29T15:55:31Z)
Resolution: won't fix
Priority: normal
Severity: tweak
Version: 3.09.0
Category: ~DO NOT USE (was: OCaml general)
Monitored by: @dra27 @alainfrisch

Bug description

In the toplevel (having loaded str.cma) enter the following statements:

let r = Str.regexp "^ +\(\([^ ]* [^ ]+\)\) +$";;
let s = " ^ and / from / my pe/tition.";;
Str.global_replace r "\1" s;;

On my 1.1GHz XP box, this takes several seconds to return. I then changed the string to " ^ and / from with added words / my pe/tition." and re-ran it: after an hour, I killed ocamlrun!

Additional information

The sample data has been reduced: the expression is useful in the code it comes from!

The regular expression is bad - the initial [^ ]* in the capture group is redundant and causes a lot of backtracking (I'm assuming) so of course I removed it to eliminate the problem in my actual code.

I'm not convinced that this is a bug in Str but thought it worth reporting just in case the exponential behaviour is unintentional.