Re: Regular Expressions Proposal

Looking more closely at the proposed regular expression extension

> 3.  Add new API
>     UBool  RegexMatcher::touchedEnd();
> 
>     Return true if the most recent attempted match or match touched the
>     end of the input string.  
>      [...]
>     The intent of this function is to allow a determination of
>     potential matches to be made while input text is incrementally
>     received.

This is turning out to have an awkward interaction with some of the 
speed optimizations.  The pattern compiler computes a minimum possible 
match length, based on items in the expression that can not be skipped. 
    If the minimum match length < the string length, the match engine is 
not even started, and there is no information about whether the start of 
the pattern matched whatever string there was.

The same thing happens with find(), which must check for possible 
matches at each potential matching point.  We've got many optimizations 
to weed out excess possible matching spots, one being too little string 
left for a match.

Within the match engine itself, the same thing happens again, but at a 
lower level.  Whenever the pattern contains a literal string that cannot 
possibly match because of too little input left, no partial match test 
is done.

I'm very hesitant to neuter these optimizations.  Performance is 
important, and it was a lot of work to bring ICU regexps up to the point 
that they were competitive with other regexp packages.

So what to do?  Some possibilities are

1.   Ignore the problem, say that the results from touchedEnd()
      are just a hint, and may be wrong.

2.   Have a mode of the RegexMatcher object for enabling touchedEnd().
      This mode would disable the optimizations.

3.   Accept the performance hit.

4.   Withdraw the proposal for touchedEnd(), at least for now.

5.   Make support for touchEnd() be a property of the Pattern, a flag
      to be set when the pattern is compiled.   This would probably
      have the least performance impact, but seems like it would be
      awkward for users.  I don't like it.

Opinions?  I lean toward either 2 or 4.

   -- Andy Heninger
      [email protected]