Tcl Source Code

Certain valid regular expressions cause [regexp]
to hang, apparently in the expression-compilation phase.
The following one-line command hangs Tcl, with memory
requirements increasing apparently without limit:

  regexp -about {(\m.*\M)*}

If the final * quantifier is removed, the bug does 
not occur.

If the grouping parentheses are removed, the bug does
not occur.

If the grouping is made noncapturing with ?:, the
bug still occurs.

Observed with Tcl 8.4.9.1 snd also 8.3.4, on Win2000.

Submitted by Jonathan Bromley,
[email protected]

Turns out this is a dup of bugs 1810038 and 1810264
(or rather, they Duped this one!).  Both fixed long
ago in time for the 8.5.0 release.

Possibly connected to 8f245009b0

Logged In: NO 

Note:

% regexp -about {(\m\M)}
1 {REG_UNONPOSIX REG_ULOCALE REG_UIMPOSSIBLE}

If the IMPOSSIBLE is genuine (and usable), then perhaps 
nfatree() in regcomp.c should 'accumulate' its return value 
from nfanode so that it retains any IMPOSSIBLE flag. 
Something like:

int ret = 0;
if (t->left != NULL) {
  ret |= nfatree(v, t->left, f);
}
if (t->right != NULL) {
  ret |= nfatree(v, t->right, f);
}
ret |= nfanode(v, t, f);
return ret;


Then compile() can check the return value:

/* build compacted NFAs for tree and lacons */
re->re_info |= nfatree(v, v->tree, debug);
if (re->re_info & REG_UIMPOSSIBLE) {
 /* throw an error */
}


More investigation needed :-)