Hi! On Sun, Mar 03, 2013 at 09:46:16AM +0100, Charles-Fran?ois Natali <cf.natali@gmail.com> wrote:

...

...

...

p = PureNTPath('c:/Downloads/pathlib.tar.gz') p.name 'pathlib.tar.gz' p.basename 'pathlib.tar' p.suffix '.gz'

I find the 'p.basename' name confusing: following POSIX conventions, 'basename' should be 'pathlib.tar.gz'.

Yes, and ntpath.py/posixpath.py follow this terminology.

I don't have another 'name' to propose for the stripped name, though.

ntpath.py/posixpath.py name these parts "root" and "extension". "Root", of course, has its own share of different connotations. Oleg. -- Oleg Broytman http://phdru.name/ phd@phdru.name Programmers don't die, they just GOSUB without RETURN.

Yes. We could call it "root" (http://en.wikipedia.org/wiki/Root_%28linguistics%29) but in this context it would be confusing. Also, it's not exactly the root since as you point there can still be a remaining suffix.

Indeed, "root" would be even more confusing.

There's "stem", too (http://en.wikipedia.org/wiki/Word_stem). With the same provision about not being the actual stem.

Also, it doesn't sound familiar (at least to me). How about "rootname", or "stripped_name" (the last one is a little too long)?

You mean for glob() (match() is just a regex-like matcher, it doesn't do any I/O).

Yes, I meant glob() (fnmatch() implementations can also be subject to DoS through stack exhaustion, but Python's implementation is based on regex).

Yes, I think we could add a `allow_recursive` argument. Is there any other DoS issue?

If by recursive you mean the '**' pattern (cross-directory match), then I'm afraid that's not enough. For example, a pattern like '*/../*/../*/../*/../*' would have the same problem: """ $ mkdir -p /tmp/foo/a /tmp/foo/b $ ~/python/cpython/python -c "from pathlib import *; p = Path('/tmp/foo'); print(list(p.glob('*/../*/../*/../*')))" [PosixPath('/tmp/foo/a/../a/../a/../a'), PosixPath('/tmp/foo/a/../a/../a/../b'), PosixPath('/tmp/foo/a/../a/../b/../a'), PosixPath('/tmp/foo/a/../a/../b/../b'), PosixPath('/tmp/foo/a/../b/../a/../a'), PosixPath('/tmp/foo/a/../b/../a/../b'), PosixPath('/tmp/foo/a/../b/../b/../a'), PosixPath('/tmp/foo/a/../b/../b/../b'), PosixPath('/tmp/foo/b/../a/../a/../a'), PosixPath('/tmp/foo/b/../a/../a/../b'), PosixPath('/tmp/foo/b/../a/../b/../a'), PosixPath('/tmp/foo/b/../a/../b/../b'), PosixPath('/tmp/foo/b/../b/../a/../a'), PosixPath('/tmp/foo/b/../b/../a/../b'), PosixPath('/tmp/foo/b/../b/../b/../a'), PosixPath('/tmp/foo/b/../b/../b/../b')] """ cf

Me wrote:

Shouldn't this particular operation return "PurePosixPath('/etc/../usr/bin/python')"?

Pardon, I ment: "PurePosixPath('../usr/bin/python')". *j

On 05.03.13 09:23, Antoine Pitrou wrote:

On Tue, 05 Mar 2013 00:33:48 +0100 Jan Kaliszewski <zuo@chopin.edu.pl> wrote:

...

1. Ad: >>> PurePosixPath('/usr/bin/python').relative('/etc') Traceback (most recent call last): ... ValueError: ...

Shouldn't this particular operation return "PurePosixPath('/etc/../usr/bin/python')"?

Think what happens if /etc is a symlink to /var/etc. (not very likely to happen for /etc, but likely to happen in the general case)

posixpath.relpath('/usr/bin/python', '/etc') returns '../usr/bin/python'. Perhaps pathlib should have an option to provide such compatible behavior. P.S. Pathlib implementation has relative_to() method. relative() method exists too but looks as unrelated.

Le Sun, 3 Mar 2013 15:12:09 +0100, Charles-François Natali <cf.natali@gmail.com> a écrit :

...

Yes. We could call it "root" (http://en.wikipedia.org/wiki/Root_%28linguistics%29) but in this context it would be confusing. Also, it's not exactly the root since as you point there can still be a remaining suffix.

Indeed, "root" would be even more confusing.

...

There's "stem", too (http://en.wikipedia.org/wiki/Word_stem). With the same provision about not being the actual stem.

Also, it doesn't sound familiar (at least to me).

How about "rootname", or "stripped_name" (the last one is a little too long)?

"rootname" is confusing because of filesystem roots, and the second is too long (not to mention it's not obvious what has been stripped). I really prefer "basename" or, if people are hostile, "stem".

...

Yes, I think we could add a `allow_recursive` argument. Is there any other DoS issue?

If by recursive you mean the '**' pattern (cross-directory match), then I'm afraid that's not enough. For example, a pattern like '*/../*/../*/../*/../*' would have the same problem:

Mmmh, I don't know how to guard against that. Perhaps by disallowing ".." in glob patterns? But the problem could still appear with symlinks. To be honest I don't think allowing untrusted users to specify a glob pattern is a very good idea. On the other hand, for the common use cases such as configuration files, the user should be trustable. Regards Antoine.

Correct me if I'm remembering wrong, but the posix basename(1) tool can strip both dirnames _and_ extensions. So, any confusion here has a solid precedent. Sent from a random iPhone On Mar 5, 2013, at 7:23, Ethan Furman <ethan@stoneleaf.us> wrote:

On 03/05/2013 01:16 AM, Antoine Pitrou wrote:

...

Le Sun, 3 Mar 2013 15:12:09 +0100, Charles-François Natali a écrit :

...

How about "rootname", or "stripped_name" (the last one is a little too long)?

I really prefer "basename" [...]

+1

-- ~Ethan~ _______________________________________________ Python-ideas mailing list Python-ideas@python.org http://mail.python.org/mailman/listinfo/python-ideas

On Mar 6, 2013, at 7:45, random832@fastmail.us wrote:

On Tue, Mar 5, 2013, at 15:29, Andrew Barnert wrote:

...

Correct me if I'm remembering wrong, but the posix basename(1) tool can strip both dirnames _and_ extensions.

So, any confusion here has a solid precedent.

Yes, but it requires you to pass in the extension.

So what about

p = '/foo/pathlib.tar.gz' p.basename() == 'pathlib.tar.gz' p.basename('.gz') == 'pathlib.tar' p.basename('.tar.gz') == 'pathlib' p.basename('.a') exception? 'pathlib.tar.gz'? p.basename(True) == 'pathlib.tar' p.basename(1) == 'pathlib.tar' p.basename(2) == 'pathlib' ?

I was just pointing out that the name already does double duty, and therefore it's a few decades too late for people to complain about confusion, not suggesting that we emulate it. But now that I see your examples, it's not a bad idea. Anyone familiar with unix will immediately understand what basename('.gz') is doing and appreciate the shortcut, and the alternate forms you provided aren't surprising. The problem is that I think people will still want a stripext/stem/root/whatever function that removes the extension without also removing the dirname. In fact, I've got a script here where one of my coworkers has written $(dirname $z)/$(basename $z .zip) to get around it. And I don't think p.basename(True, False) is a viable answer. Besides, what names would you give the two flags? If there were good names for those, there would be good names for the two separate functions, right? Personally, I don't have a problem with the stem or stripext suggestions (although to me, the former implies stripping all extensions, the latter just one), but I guess they haven't gotten much traction.

From: "random832@fastmail.us" <random832@fastmail.us> Sent: Wednesday, March 6, 2013 11:15 AM

On Wed, Mar 6, 2013, at 13:28, Andrew Barnert wrote:

...

The problem is that I think people will still want a stripext/stem/root/whatever function that removes the extension without also removing the dirname. In fact, I've got a script here where one of my coworkers has written $(dirname $z)/$(basename $z .zip) to get around it. …

Well, whatever you do is competing with p[:-len('.gz')]

Only the "remove extension by name" is competing with that. The "remove any and all extensions" or "remove 1 extension" or "remove n extensions" cases—which I think are more common—are not. Of course they _are_ competing with various uses of partition/rpartition/split/rsplit. But you could make the same argument for everything in a path library—p.dirname() is competing with p.rpartition(pathsep)[0], and 'p / 'foo' is competing with p + pathsep + 'foo', and so on. As I understand it, the reason to have a path API is to provide a "one way to do it" that's obvious, readable, and hard to get wrong. And I think p.stripext('.gz') or p.stripext(2) or p.stripext() are better than p[:-len('.gz')] or p.rsplit('.', 2)[0] or p.partition('.')[0] in that regard. Except for the name, which nobody's come up with a good suggestion for, and the fact that we probably don't want to cram all three versions of the operation into one function, or even necessarily support all three at all.

(and in shell, your co-worker could have done ${z%.zip} in ksh/bash/POSIX) - unless you have an example of an OS where the 'extension' component doesn't simply append at the end (well, I suppose they're not case-sensitive on windows - and how much weird long/short filename stuff does pathlib do on windows?)

Funnily enough, according to a comment, this was intended to handle all-caps .ZIP on Windows under cygwin. I don't know if it actually works (or, for that matter, if %.zip would have worked), as I don't have a Windows box with cygwin installed handy. But that's beside the point. The point is that people want a method that removes extensions (whether by name or otherwise) that doesn't also remove dirnames. And if you force them to come up with such a method themselves, they're not necessarily going to come up with a good one. I'm sure if we had your extended basename but no stripext, someone would write p.dirname()/p.basename('.zip').

On Mar 6, 2013, at 14:14, MRAB <python@mrabarnett.plus.com> wrote:

On the other hand, p.stripext('.zip') feels OK because it suggests that you're stripping off the '.zip' extension (compare with str.strip), but would that mean that you'd expect p.stripext() also to strip off the extension, whatever it was?

Given the earlier responses on this thread, I think it's safe to say that plenty of people, like Paul Moore, would either expect it, or complain about its nonexistence. Anyway, I think getting side-tracked on random's suggestion (which, by the way, is almost entirely my fault) has detracted from the main point. Even if we _did_ have an extended basename that can strip both dirname and extension, with every option you could possible desire, people would _still_ want a method that strips the exception only. And calling that method basename (or root) is ambiguous and misleading to people who expect that name to mean pulling off directories rather than extensions. My original point was that Unix created this confusion by overloading the meaning of basename decades ago. The question is whether that's sufficient justification to use the name in python. I don't think it is (again, I'd prefer stem or splitext), but it was at least worth asking.

...

...

...

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...

...

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 "[!...]".

What's not difficult? Avoiding DoS with arbitrary glob patterns? If yes, please share your idea :-)

Compile the glob pattern to an NFA and simulate the NFA efficiently (using Thompson's algorithm or even backtracking with memoization, rather than plain backtracking).

Well, I'm sure it would be much better, but that would be a rather large piece of code, which would probably belong to a new regex engine, no?

I wrote an alternative regex implementation (it's on PyPI). It's a lot more resistant to catastrophic backtracking. What's need for fnmatch is a lot simpler than that! :-)

Yes, I know about your regex implementation, but it looks like it's not going in anytime soon. Do you think you could come up with a reasonable - i.e. self-contained - patch for fnmatch?

On 2013-03-06 22:03, Charles-François Natali wrote:

...

Compile the glob pattern to an NFA and simulate the NFA efficiently (using Thompson's algorithm or even backtracking with memoization, rather than plain backtracking).

Well, I'm sure it would be much better, but that would be a rather large piece of code, which would probably belong to a new regex engine, no?

...

I wrote an alternative regex implementation (it's on PyPI). It's a lot more resistant to catastrophic backtracking. What's need for fnmatch is a lot simpler than that! :-)

Yes, I know about your regex implementation, but it looks like it's not going in anytime soon. Do you think you could come up with a reasonable - i.e. self-contained - patch for fnmatch?

I think it's worth looking at!

On Wed, Mar 6, 2013 at 3:20 PM, MRAB <python@mrabarnett.plus.com> wrote:

I wrote an alternative regex implementation (it's on PyPI). It's a lot more resistant to catastrophic backtracking.

How resistant? If it's possible to have catastrophic backtracking even if groups and backreferences aren't involved, then it wouldn't solve the fnmatch DOS problem. -- Devin

On Wed, Mar 6, 2013 at 5:40 PM, MRAB <python@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. 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? -- Devin

On Wed, Mar 6, 2013 at 6:25 PM, MRAB <python@mrabarnett.plus.com> wrote:

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.

We seem to be talking past each other. I already know all this. I am asking you to justify your claim that if glob was based on regex, instead of re, it would be free of DOS attacks. Because of your confusion, I expect you didn't really mean to claim that. I inferred it because when you were asked for an approach that would solve DOS attacks against glob, you replied by saying that you wrote a regex module that is more resistant to such things. I apologize if I misunderstood. -- Devin

Le Thu, 07 Mar 2013 11:50:31 +0000, MRAB <python@mrabarnett.plus.com> a écrit :

I didn't say that it should be based on regex. What I meant was that it didn't seem that difficult compared to the regex module.

That module is more resistant to catastrophic backtracking and some of its tricks could be used for the much simpler fnmatch to make a new implementation of _that_ more resistant to the problem. I'm currently thinking about the details.

Keep in mind it shouldn't slow down the general (non-hostile) use case. Regards Antoine.

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

This looks really promising. Could one of you open an issue on the tracker and attach a patch? Note that there's a problem with a current implementation: AssertionError: False is not true : expected 'abc' to match pattern '???*'

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

On 07/03/2013 15:28, Charles-François Natali wrote:

...

And here's a new implementation:

Thanks. Could you post this on the tracker? Patches sent to mailing lists tend to get lost, and we've already hijacked Antoine's thread long enough :-)

Done, and apologies to Antoine. :-)