[Python-ideas] Updated PEP 428 (pathlib)

[MRAB]

On 2013-03-06 17:51, MRAB wrote:
> On 2013-03-06 17:08, Charles-François Natali wrote:
>>>>>> fnmatch.fnmatch('a'*50, '*a*'*50) # weird how the pattern/string order is reversed from re.match
>>>
>>> That will take about 200 years to complete with CPython. Maybe a
>>> little less, if you're running a particularly fast computer. ;)
>>>
>>> Is that the sort of DoS issue you are looking for?
>>
>> Exactly (the complexity of a typical ad-hoc fnmatch() implementation
>> is the reason some servers like vsftpd use their own version, and it's
>> even worse with a regex-based implementation as you notice).
>>
>> Now, the question is whether we want to try to mitigate this or not...
>>
> It's not something I've ever used, but it doesn't look that difficult
> compared to regex if all it has is "*", "?", "[...]" and "[!...]".
>
Here's a very simple, all-Python, implementation I've just cooked up:

def fnmatch(name, pattern):
     positions = [(0, 0)]

     while positions:
         name_pos, pattern_pos = positions.pop()

         if pattern_pos >= len(pattern):
             if name_pos >= len(name):
                 return True
         elif pattern[pattern_pos] == '*':
             if pattern_pos == len(pattern) - 1:
                 return True

             positions.append((name_pos, pattern_pos + 1))

             if name_pos < len(name):
                 positions.append((name_pos + 1, pattern_pos))
         elif pattern[pattern_pos] == '?':
             if name_pos < len(name):
                 positions.append((name_pos + 1, pattern_pos + 1))
         elif pattern[pattern_pos] == '[':
             if name_pos < len(name):
                 negative = pattern[pattern_pos + 1] == "!"
                 pattern_pos += 2 if negative else 1

                 close_pos = pattern.find(']', pattern_pos)
                 if close_pos >= 0:
                     if (name[name_pos] in pattern[pattern_pos : 
close_pos]) != negative:
                         positions.append((name_pos + 1, close_pos + 1))
         elif name_pos < len(name) and name[name_pos] == 
pattern[pattern_pos]:
             positions.append((name_pos + 1, pattern_pos + 1))

     return False