[Python-ideas] Updated PEP 428 (pathlib)

MRAB python at mrabarnett.plus.com
Thu Mar 7 16:13:38 CET 2013


On 07/03/2013 02:26, MRAB wrote:
> 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:
>
[snip]
And here's a new implementation:

def fnmatch(name, pattern):
     saved_name_pos, saved_pattern_pos = 1, -1

     name_pos, pattern_pos = 0, 0

     while True:
         retry = False

         if pattern_pos >= len(pattern):
             if name_pos >= len(name):
                 return True

             retry = True
         elif pattern[pattern_pos] == '*':
             saved_name_pos, saved_pattern_pos = name_pos + 1, pattern_pos

             pattern_pos += 1
         elif pattern[pattern_pos] == '?':
             if name_pos < len(name):
                 name_pos += 1
                 pattern_pos += 1
             else:
                 retry = True
         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:
                         name_pos += 1
                         pattern_pos = close_pos + 1
                     else:
                         retry = True
                 else:
                     retry = True
             else:
                 retry = True
         elif name_pos < len(name) and name[name_pos] == 
pattern[pattern_pos]:
             name_pos += 1
             pattern_pos += 1
         else:
             retry = True

         if retry:
             if saved_pattern_pos < 0:
                 return False

             name_pos, pattern_pos = saved_name_pos, saved_pattern_pos




More information about the Python-ideas mailing list