[Patch] Add regex_constants::__polynomial

[Tim Shen <timshen at google dot com>]

On Tue, Feb 17, 2015 at 1:54 AM, Jonathan Wakely wrote:
> On 16/02/15 22:10 +0000, Tim Shen wrote:
>>
>> Hi Jon,
>>
>> The Thompson NFA algorithm (BFS approach) in libstdc++ regex exists for a
>> while, and I do think we can add it to the standard as a flag
>> regex_constants::syntax_option_type::polynomial, which requires the regex
>> compiler to produce a NFA that never consumes exponentially large space
>> and
>> and exectuer not to consume exponential time for matching. It's good for
>> security reasons.
>>
>> When compiling a regex with this flag, a back-reference in regex will
>> cause
>> a regex_error::error_type::unexpected_backref exception, since matching a
>> backref in polynomial time is as hard as proving P=NP :P. I think that's
>> the only requirement of this flag.
>>
>> re2 <https://code.google.com/p/re2/> is a library that actually implements
>> this requirement.
>>
>> Do you think it's an appropriate proposal?
>>
>> Thanks! :)
>
>
> The names would have to be uglified so e.g. __polynomial and
> __unexpected_backref but I think it's an excellent idea.

As discussed with Jon, we think it's a good idea to add the
__polynomial as an extension flag for exposing our BFS executer
(Thompson NFA matching algorithm).

Currently ECMAScript doesn't correctly support Thompson NFA though;
I'm actually (slowly) doing a refactoring starting with ECMAScript,
but I think it's still good to let users use it earlier.

Bootstrapped and tested.

Thanks!


-- 
Regards,
Tim Shen

Attachment: a.diff
Description: Text document