[Python-ideas] Updated PEP 428 (pathlib)

[MRAB]

On 2013-03-06 22:49, Devin Jeanpierre wrote:
> On Wed, Mar 6, 2013 at 5:40 PM, MRAB <python at mrabarnett.plus.com> wrote:
>> If there aren't capture groups, then you can use a DFA.
>
> You can use a variant of DFA even if there are capture groups, it just
> takes more effort.
>
>> The re and regex modules use NFA because of the various other features
>> required.
>
> I take it you mean that both the re and regex modules use backtracking search.
>
Yes.

> I was asking whether or not it can reach the exponential time
> worst-case on regexps without capture groups. If the answer is no, as
> you seem to be implying, then how does it prevent a DOS attack?
>
You _can_ have catastrophic backtracking without capture groups. You've
already seen an example in ".*a.*".

It gets worse when you can have repeated repeats, for example "(?:.*)*".

The difference with fnmatch is that you don't care _where_ various
parts match (there are no capture groups), only _whether_ it matches,
and then only whether or not _all_ of it matches.